4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 4 4 #### #JF# #..# #..# ans : 3 전에 푼 토마토 문제와 비슷한 느낌이지만 굉장히 다르다. 불과 지훈이가 동시에 BFS를 돌리면 될 것 같지만 사실 무조건 불부터 돌려야 한다. 같은 시간대에 불이 도달할 수 있으면 지훈이는 해당 칸에 못 가기 때문이다. 동시에 돌리는 것처럼 큐 한 개로 처리하면 우선순위를 고려하기 굉장히 번거롭고 오래 걸린다. 따라서 불부터 BFS를 돌리고, 지훈이 도착시간이 불보다 작으면 방문 가능한 칸..

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 예제 6 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 ans : 8 최단 경로를 보고 바로 BFS를 떠올렸다. 조금 다른 점은 토마토가 여러 개인 경우 동시에 여러 시작점에서 BFS를 시작해야 한다는 것이다. 토마토들 간의 우선순위는 없으니 간단하게 큐에 시작점을 모두 넣고 BFS를 돌리면 된다. 구현은 전에 푼 문제와 거의 똑같다. 조금 다른건 토마토가 없는 칸, 즉 다른 문제의 벽에 해당하는 칸만 ..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 예제(더 많은 예제는 링크에 있습니다.) 4 6 101111 101010 101011 111011 ans : 15 BFS의 가장 대표적인 문제 중 하나로, 최단경로 탐색 문제이다. 최단 경로가 왜 BFS냐면, 여러 갈래 길이 나왔을 때 마치 BFS처럼 너비 우선으로 길을 찾으면서 진행하기 때문이다. 최단경로가 나오면 BFS를 가장 먼저 고려해 보자. 기본적인 BFS 구현에서 visited 배열만 dist 배열로 바꿔서 거리를 표시해 주면 된다. dist의 모든 칸을 -1로 두고, BFS의 시작..