BFS

문제 https://leetcode.com/problems/minimum-depth-of-binary-tree/description/ 주어진 이진트리에서 트리의 최소 깊이를 구하여라. 최소 깊이는 루트 노드부터 가장 가까운 리프 노드까지 내려가는 최단 거리에 있는 노드의 수이다. Note: 리프 노드는 자식 노드를 가지고 있지 않다. 풀이 1. BFS - 너비 우선 탐색 fun minDepth(root: TreeNode?): Int { if(root == null) return 0 val q = ArrayDeque() q.add(root) var depth = 1 while (q.isNotEmpty()) { val curSize = q.size repeat(curSize) { val curNode = q..

문제 (Gold 4) https://www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 풀이 문제 해석 1. 일반 목초지 사이는 상하좌우 모두 움직일 수 있다. 2. 중간에 다리가 있다면, 다리를 꼭 건너야 한다. 즉, 소(2,2)는 소(2,3)까지 다리를 건너야할 수도 있지만, 그 길을 회피해 회색 화살표 길로 갈 수 있다. 소(3,3)은 다른 목초지에 가려면 무조건 다리를 건너야 하므로, 모든 소와 유효한 쌍이 된다..

문제 (Silver 2) https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 풀이 1. 양 또는 늑대가 있는 영역을 검사 (BFS) 2. 그래프를 돌며 양과 늑대의 위치 저장 3. 탐색 후, 양과 늑대 리스트 크기 비교 후 map에 반영 코드 더보기 import java.util.*; import java.io.*; public class Main { static int[] di = {-1,0,1,0}; static int[] dj =..

문제 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 풀이 전형적인 BFS 시뮬레이션 문제! 모든 로직의 순서와 불이 번지는 과정만 꼼꼼히 작성해주면 된다. BFS 로직 순서 1. Depth가 늘어날 때 마다 불 확산 2. 가려는 길에 불이 있으면 Continue 3. 종료 조건 확인 4. 상근이 이동 가능 경로 탐색 불이 번지는 과정 1. 불이 새로 번진 곳을 저장할 리스트 선언 2. 현재 불 리스트를 돌며 새로 번진 리스트에 추가 3. 현재 불 리스트를..