본문 바로가기
반응형

Problem Solving/BOJ228

백준 2638번 치즈 - 스위프트(Swift) 풀이 + 그림 설명 1. 가장자리 아무 칸에서나 시작해 DFS/BFS로 인접한 모든 칸들을 외부 공기 처리한다. 2. 치즈들을 모두 순회하면서 녹을지 말지를 결정한다. 3. 치즈가 남지 않을 때까지 1-2를 반복한다. 1. 가장자리 아무칸에서나 시작해 DFS/BFS로 인접한 모든 칸들을 외부 공기 처리한다. 가장자리에는 치즈가 오지 않으므로 항상 외부 공기가 있는 칸이다. 치즈로 둘러싸여 있는 내부 공기 칸과 구분하기 위해 매시간마다 가장자리에서 시작하는 BFS/DFS를 돌면서 인접한 칸들을 모두 외부 공기 칸으로 처리해준다. 좌측과 같은 초기 상황이라고 하면, 먼저 우측 그림처럼 외부 공기 처리를 해준다. 내부 공기와는 다르게 처리되고 있는 것에 유의한다. 2. 치즈들을 모두 순회하면서 녹을지 말지를 결정한다. 매 시간마.. 2022. 1. 26.
백준 14938번 서강그라운드 - 스위프트(Swift) 풀이 1. 모든 정점에 대해 각 정점에서 모든 정점으로 가는 거리를 플로이드 와샬 알고리즘을 사용하여 구한다. 2. 모든 정점에 대해 해당 정점과의 거리가 m이하인 정점들을 탐색하여 해당 정점에 낙하했을 때 얻을 수 있는 아이템 수를 구한다. 3. 2번에서 구한 값 중 최댓값을 출력한다. 1. 모든 정점에 대해각 정점에서 모든 정점으로 가는 거리를 플로이드 와샬 알고리즘을 사용하여 구한다. 각 정점에 낙하하는 모든 경우를 고려한 뒤 최적해를 골라야 한다. 또한, 어떤 정점에 낙하했을 때 얻을 수 있는 아이템 수를 알려면, 해당 정점에서 나머지 정점으로의 거리를 전부 알아야 한다. 따라서 모든 정점에 대해 나머지 정점으로의 거리를 구하는 플로이드 와샬 알고리즘을 사용한다. N=100이므로 O(N^3)도 제한시간.. 2022. 1. 26.
백준 17070번 파이프 옮기기 1 - 스위프트(Swift) 풀이 1. dp(row, col, direction) = 왼쪽 끝이 (row,col)에 위치하고 direction 방향으로 놓인 파이프를 (N,N)으로 옮기는 방법의 수 2. dp(row, col, direction) = ∑ dp(파이프가 이동할 수 있는 위치, 방향) 1. dp(row, col, direction) = 왼쪽 끝이 (row,col)에 위치하고 direction 방향으로 놓인 파이프를 (N,N)으로 옮기는 방법의 수 DP라는 방법만 떠올리고 나면 특별히 고려해줄 점 없이 그냥 구현하면 된다. dp(row, col, direction)을 위와 같이 정의한다. 2. dp(row, col, direction) = ∑ dp(파이프가 이동할 수 있는 위치, 방향) 파이프를 이동시킬 수 있는 모든 방법을 .. 2022. 1. 26.
백준 15686번 치킨 배달 - 스위프트(Swift) 풀이 1. M개 이하의 치킨집을 고르는 모든 경우에 대해 도시의 치킨 거리를 계산한다. 1. M개 이하의 치킨집을 고르는 모든 경우에 대해 도시의 치킨 거리를 계산한다. 단순 구현 문제이다. 브루트포스로도 시간 안에 풀 수 있다. M개 이하의 치킨집을 이미 골랐다고 가정했을 때, 도시의 치킨 거리를 구하는 데는 O(2N * 13)이 든다. M개 이하의 치킨집을 고르는 경우의 수는 적어도 2^13보다는 적으므로 최종 시간 복잡도는 O(2N * 13 * 2^13) = O(2^14 * 13 * N)이고, N=50이므로 연산 횟수 10,649,600으로 AC를 받기에 충분한 시간 복잡도이다. import Foundation typealias Chicken = (row: Int, col: Int) typealias C.. 2022. 1. 25.
백준 17352번 여러분의 다리가 되어 드리겠습니다! - 스위프트(Swift) 풀이 1. 모든 다리에 대해 다리로 이어진 두 섬을 union 한다. 2. 1번 섬과 이어지지 않은 섬, 즉 find(i) ≠ find(1)인 섬을 찾아 (1, i)를 출력한다. 1. 모든 다리에 대해 다리로 이어진 두 섬을 union 한다. 다리로 이어진 두 섬은 왕복할 수 있다. 1 - 2가 연결되어 있고, 1 - 3이 연결되어 있으면 2 - 3으로도 갈 수 있다. union 연산과 같다. 2. 1번 섬과 이어지지 않은 섬, 즉 find(i) ≠ find(1)인 섬을 찾아 (1, i)를 출력한다. 어떤 두 섬이든 다리로 왕복할 수 있으려면 1번 섬에서도 어느 섬으로든 갈 수 있어야 한다. 따라서 1번 섬과 부모가 다른 섬을 찾아 출력해주면 된다. 1번 섬이 아니더라도 아무 섬이나 하나 기준으로 잡고, 그 .. 2022. 1. 25.
반응형

티스토리툴바