[알고리즘] 코테 유형 분석 6. BFS

안녕하세요 이번 시간에는 BFS의 문제 유형을 분석해보는 시간을 갖도록 하겠습니다. BFS 문제를 풀 때 고려해야 할 사항은 모든 그래프가 연결되어 있는지를 체크하는 것입니다. DFS의 경우 하나의 노드를 깊게 탐색하기 때문에 최단 거리 혹은 최소 시간을 탐색하는데 있어서 먼저 최단 거리가 아닌 노드를 방문할 가능성이 존재하기 때문에 잘못된 결과를 출력합니다. 하지만 BFS는 하나의 시작점에서 인접한 그래프로 이동하면서 탐색하기 때문에 모든 그래프가 연결되어 있다면 최단 거리를 구할 수 있습니다.

첫 번째 유형은 시작점부터 도착점까지의 최단 거리 혹은 최소 시간을 구하는 문제입니다. BFS 특성 상 큐에 들어가 있는 원소들이 카운트 순서대로 이동하기 때문에 도착값을 가장 먼저 가지는 큐의 원소가 곧 도착점에 도착한 것이 됩니다. 이를 이용해서 최단 거리 또는 최소 시간을 구할 수 있습니다.

백준 2644(촌수 계산) 문제의 경우 두 사람의 촌수를 출력하는 문제입니다. 촌수는 곧 인접 리스트에서 두 사람 간의 최소 거리를 의미하므로 인접 리스트 생성 후 한 사람의 위치에서 bfs로 탐색하여 다른 사람에 도착했을 경우 탐색한 노드의 개수를 출력합니다.

백준 2178(미로 탐색) 문제의 경우 (1,1) 에서 (N,M)까지 이동할 때 지나는 최소 칸 수를 구하는 문제입니다. (1,1) 지점에서 bfs를 시작하여 1칸씩 이동시키면서 (N,M)에 도달했을 경우 거리를 출력합니다.

백준 7562(나이트의 이동) 문제의 경우 나이트가 최소 몇 번 이동했을 때 해당 칸으로 이동이 가능한지를 구하는 문제입니다. 현재 지점에서 나이트가 이동할 수 있는 거리를 배열에 넣어 bfs로 이동시키면서 해당 위치에 도달했을 경우의 카운트값을 출력합니다.

백준 2206(벽 부수고 이동하기) 문제의 경우 한 개의 벽을 부수고 이동 가능할 때 최단 거리를 구하는 문제입니다. 백트래킹을 이용하면 시간 초과가 발생하기 때문에 벽을 부쉈을 때와 벽을 부수지 않았을 때의 상태를 각각 저장하여 3차원 배열로 처리합니다. 이 때 도착 지점에 먼저 도달한 경우가 최솟값이기 때문에 bfs로 탐색합니다.

백준 16236(아기 상어) 문제의 경우 물고기를 잡아먹을 수 있는 최대 시간입니다. bfs를 이용해서 먹을 수 있는 물고기까지 이동하며, 먹을 수 있는 물고기가 여러 마리일 경우 모두 큐에 넣고 실제로 먹는 물고기는 큐에서 poll한 값만을 먹는 방식으로 구현합니다.

백준 13460(구슬 탈출2) 문제의 경우 최소 몇 번만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지를 구하는 문제입니다. 한 칸씩 bfs를 하는 것이 아닌 벽이나 다른 구슬이 나올 때까지 계속 이동하는 방식으로 bfs로 탐색합니다.

백준 2589(보물섬) 문제의 경우 보물이 묻혀 있는 두 곳 같의 최단 거리를 구하는 문제입니다. bfs로 탐색하면서 큐에 들어있는 카운트값의 최댓값을 출력하면 됩니다.

백준 6593(상범 빌딩) 문제의 경우 동서남북상하의 빌딩을 얼마나 빨리 탈출할 수 있는지를 구하는 문제입니다. 3차원 배열을 생성하여 6개 방향으로 bfs를 진행하면 됩니다.

백준 18352(특정 거리의 도시 찾기) 문제의 경우 X에서 출발해서 최단 거리가 K만큼 이동했을 때 도달 가능한 도시 수를 구하는 문제입니다. 주어진 위치에서 bfs를 통해 탐색하면서 카운트가 K일 경우 정답 큐에 추가하는 방식으로 문제를 풀 수 있습니다.

두 번째 유형은 특정 오브젝트를 기준으로 확장하는 문제입니다. 이 경우 방문 여부를 체크할 뿐만 아니라 현재 지점에서의 상태값을 같이 고려해야 합니다. 또한 여러 개의 오브젝트가 존재할 경우 오브젝트를 확장할 때의 순서가 중요합니다. 만약 한번에 확장하지 않고 그때그때 확장하게 된다면 다른 확장 가능한 오브젝트가 이미 확장된 상태값에 영향을 받아 잘못된 결과값을 출력할 수 있습니다.

백준 7576(토마토) 문제의 경우 창고에 보관하는 토마토들이 며칠이 지나면 다 익는지의 최소 일수를 구하는 문제입니다. 익은 토마토의 cnt값을 큐에 같이 저장하여 bfs를 진행하여 익지 않은 토마토를 익은 토마도로 상태를 변경해줍니다. 토마토가 다 익는 경우인 큐가 다 빌 경우 cnt의 최댓값을 출력하면 됩니다.

백준 3055(탈출) 문제의 경우 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 구하는 문제입니다. bfs로 고슴도치를 이동시키고 모든 물은 "한번에" 이동시킵니다.

백준 2146(다리 만들기) 문제의 경우 가장 짧은 다리를 하나 놓아 두 대륙을 연결하는 방법을 구하는 문제입니다. dfs를 이용해서 각 섬의 id를 부여하고 각 섬 별로 bfs 탐색을 진행하여 경계값을 1칸씩 확장해나갑니다. 이 때 다른 대륙과 만나는 경우 확장한 만큼이 다리 길이가 되며, 이 때 확장값의 최솟값을 출력합니다.

백준 5427(불) 문제의 경우 얼마나 빨리 불이 난 빌딩을 탈출할 수 있는지를 구하는 문제입니다. 탈출 문제와 마찬가지로 bfs로 이동시키면서 불은 한번에 인접칸으로 이동시킵니다.

백준 16234(인구 이동) 문제의 경우 인구 이동이 며칠 동안 발생하는지를 구하는 문제입니다. bfs로 탐색하여 주어진 경계값 내인 경우 따로 저장하여 연합의 총 인구 수와 연합의 칸 개수를 최신화합니다. bfs 탐색이 완료되면 (인구수 / 칸 수)로 연산한 값으로 선택된 칸들을 모두 바꾸고 이어서 진행하는 방식으로 풀 수 있습니다.

백준 1325(효율적으로 해킹하기) 문제의 경우 A가 B를 신뢰하는 경우 B를 해킹했을 때 A도 해킹된다고 하면 가장 많이 해킹할 수 있는 컴퓨터를 구하는 문제입니다. 자기 자신을 신뢰하는 연결된 컴퓨터 개수를 bfs로 탐색 후 최댓값을 출력합니다. 여기서 주의할 점은 신뢰관계를 역으로 그래프를 생성하여 해당 포인트에서 직접 해킹을 진행할 경우 반복되는 노드들이 많아 시간 초과가 발생하기 때문에 신뢰관계 방향대로 그래프를 생성하여 자신을 신뢰하는 연결된 컴퓨터 수를 구하는 것이 핵심입니다.

세 번째 유형은 연산을 수행할 수 있는 경우의 수가 여러 개 존재하는 문제입니다. bfs 특성 상 여러 연산을 같은 횟수로 처리해야 할 경우 연산의 결과를 카운트를 같게 하여 큐에 넣으면 한번에 탐색이 가능합니다.

백준 1697(숨바꼭질) 문제의 경우 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구하는 문제입니다. X-1, X+1, X x2 세 연산을 각각 수행하여 범위 내에 존재할 경우 큐에 추가하여 bfs 탐색을 진행합니다.

백준 5014(스타트링크) 문제의 경우 G층에 도착하기 위해 최소 눌러야 하는 버튼 수를 구하는 문제입니다. 숨바꼭질 문제와 마찬가지로 U와 D만큼 이동한 값이 범위 내에 있다면 큐에 추가하여 bfs 탐색을 진행합니다.

백준 9019(DSLR) 문제의 경우 A에서 B로 변환하기 위해 필요한 최소한의 명렁어 나열 수를 구하는 문제입니다. D,S,L,R 연산을 각각 수행한 결과를 큐에 넣어 bfs 탐색을 진행하여 가장 먼저 도착하는 값의 cnt를 출력합니다.

백준 1039(교환) 문제의 경우 i번 위치와 j번 위치를 바꾸는 연산을 K번 했을 때 나오는 수의 최댓값을 구하는 문제입니다. 반복문을 이용하여 i번 위치와 j번 위치를 바꾼 결과를 큐에 넣어 bfs 탐색을 진행하여 카운트가 K일 경우 최댓값으로 갱신하면 됩니다. 이 때 변환 연산 이후 앞 자리가 0으로 시작하는 경우는 불가능하므로 큐에 추가하지 않습니다.

백준 2251(물통) 문제의 경우 A와 B는 비어있고 C가 가득 차있을 때 물통을 가득찰 때까지 부을 수 있는 경우 A가 비어있을 때 C에 담겨있을 수 있는 물의 양을 모두 출력하는 문제입니다. 물통의 개수가 3개밖에 되지 않기 때문에 물을 담을 수 있는 모든 경우의 수인 3P2 = 6을 크기로 하는 배열에 등록합니다. 이 후 물을 담을 때 보내는 쪽의 모든 물을 전부 담은 후 물통 크기보다 담은 물이 많을 경우 그 차이만큼 담은 물통에 추가하고 받은 물통은 그 물통의 크기만큼 채우면서 bfs를 진행하여 조건에 맞는 C의 값을 정답 큐에 추가합니다.