import sys
from collections import deque
input = sys.stdin.readline
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
n, m = map(int, input().split())
graph = [[0] * m for _ in range(n)]
visited = [[-1] * m for _ in range(n)]
def BFS(i, j):
que = deque()
que.append((i, j))
visited[i][j] = 0
while que:
curr = que.popleft()
for k in range(4):
x = curr[0] + dx[k]
y = curr[1] + dy[k]
if x >= 0 and y >= 0 and x < n and y < m:
if graph[x][y] != 0 and visited[x][y] < 0:
visited[x][y] = visited[curr[0]][curr[1]] + 1
que.append((x, y))
for i in range(n):
numbers = list(input())
for j in range(m):
graph[i][j] = int(numbers[j])
BFS(0, 0)
print(visited[n-1][m-1] + 1)위 문제는 BOJ 2178번 미로탐색 문제이다.
위와 같이 거리를 측정하는 문제들은 bool 형의 visited 배열을 두지 않고도 방문 여부를 알 수 있다. (대신 visited 배열의 초기값을 -1로 두어 visited ≥ 0 인 경우 방문으로 간주하는 것이다)
⭐보통 시작점 - 도착점까지의 거리를 구하는 문제가 나오면 이런 알고리즘을 사용하는 경우가 많다.
from collections import deque
import sys
input = sys.stdin.readline
m, n = map(int, input().split())
arr = []
que = deque()
res = 0
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
for _ in range(n):
arr.append(list(map(int, input().split())))
for i in range(n):
for j in range(m):
if arr[i][j] == 1:
que.append((j , i))
def bfs():
while que:
x, y = que.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < m and 0 <= ny < n and arr[ny][nx] == 0:
arr[ny][nx] = arr[y][x] + 1
que.append((nx, ny))
bfs()
for i in arr:
for j in i:
if j == 0:
print(-1)
exit(0)
res = max(res, max(i))
print(res - 1)위 문제는 BOJ 7576 토마토 문제이다.
위 문제를 보면 알 수 있다시피, 이 문제는 시작점이 여러 개다. 익은 토마토가 1개일 수도 있고, 1개가 아닐 수도 있다.
단편적으로 생각해봤을 때 이중반복문을 돌려서 익은 토마토가 있을 때마다 BFS를 실행하는 방안을 생각해볼 수 있다.
하지만 그 방법으로 실행하면, **BFS의 시간복잡도가 O(NM)**이 되고, **토마토도 최대 O(NM)**개 존재할 수 있으니 시간복잡도는 **O(
해결방안
해결방안은 생각보다 단순하다. 시작점을 모두 큐에 넣고 BFS를 돌리면 끝난다.
코드에서 보면 알 수 있다시피 n개의 시작점 중 먼저 도착했을 경우에 arr 값을 바꾸기 때문에 더 늦게 도착한 시작점은 값을 바꿀 수가 ❌
추가적으로 시작점이 여러 개인 BFS 문제를 풀 때 알아둬야 할 특징이 한 개 더 있다.
- 위 알고리즘에서는 BFS를 돌 때 que에 쌓이는 순서는 반드시 거리순으로 쌓인다!!!
import sys
from collections import deque
arr = []
n, m = map(int, input().split())
for i in range(n):
arr.append(list(input().rstrip()))
visited_fire = [[-1 for _ in range(1001)] for _ in range(1001)]
visited_person = [[-1 for _ in range(1001)] for _ in range(1001)]
que_fire = deque()
que_person = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(n):
for j in range(m):
if arr[i][j] == 'F':
que_fire.append((i, j))
visited_fire[i][j] = 0
elif arr[i][j] == 'J':
que_person.append((i, j))
visited_person[i][j] = 0
while que_fire:
x, y = que_fire.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if visited_fire[nx][ny] >= 0 or arr[nx][ny] == '#':
continue
visited_fire[nx][ny] = visited_fire[x][y] + 1
que_fire.append((nx, ny))
while que_person:
x, y = que_person.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
print(visited_person[x][y] + 1)
sys.exit()
if visited_person[nx][ny] >= 0 or arr[nx][ny] == '#':
continue
if visited_fire[nx][ny] != -1 and visited_fire[nx][ny] <= visited_person[x][y] + 1:
continue
visited_person[nx][ny] = visited_person[x][y] + 1
que_person.append((nx, ny))
print("IMPOSSIBLE")위 문제는 BOJ 4179번 불! 문제이다.
위 문제는 지훈이는 이동가능 한 칸을 불에 타기 전에 이동해야한다.
이 조건을 구현하는 것이 생각보다 까다로운데, 생각을 해보면 continue 조건으로 넘어가는 if문을 한 가지 더 추가하면 된다.
- 배열의 범위를 넘어가거나
- 이미 방문했거나, 장애물이 있거나
- 지훈이가 도착하기 전에 이미 불에 타버렸거나
1, 2번까지는 원래 우리가 구현하던 방법이지만, 3번을 구현하기 위해서는 생각이 필요하다.
⭐해결방법
불에 대한 bfs와 지훈이에 대한 bfs를 따로 돌리면 된다.
불에 대한 bfs를 먼저 돌려, 3번 조건을 구현하기 위해 (지훈이가 해당 점에 도착하기 전 위치에서의 거리 + 1) ≥ (불이 도착한 거리)를 비교하여 continue로 넘겨주면 된다.
이렇게 bfs를 2개 돌리면 된다.
from collections import deque
visited = [0] * (10 ** 5 + 1)
def bfs(visited):
que = deque()
que.append(N)
while que:
tmp = que.popleft()
if tmp == K:
return visited[tmp]
for i in (tmp - 1, tmp + 1, tmp * 2):
if 0 <= i <= (10 ** 5) and not visited[i]:
visited[i] = visited[tmp] + 1
que.append(i)
N, K = map(int, input().split())
print(bfs(visited))위 문제는 BOJ 1697번 숨바꼭질 문제다.
마지막 유형은 이게 BFS가 맞나 싶기도 할 것이다.
언뜻 봤을 때는 이분 탐색으로도 해결이 가능해보이고, 그리디, DP 등의 방법으로도 해결이 가능해보인다.
하지만 이 문제는 BFS를 사용해서 풀어야한다.
⭐해결방법 위 코드처럼 이동가능한 범위를 dx, dy 배열처럼 놓고 반복문을 돌리면 된다.
이 문제가 BFS 문제라는 것을 알아차리기만 하면 사실 풀이 방법은 매우 쉽지만, 이 문제에서 정확하게 짚고 넘어가야 할 부분은 BFS의 범위이다.
위 문제를 기준으로 점의 범위가 0 ≤ N ≤ 100,000 이니까 100,000으로 설정하면 되지 않을까? 라고 때려 맞추기 쉽다.
하지만 문제에서 수빈이가 100,000을 넘어가면 안된다는 조건이 없기 때문에 이 부분은 함부로 단정지으면 안된다.
- 상식적으로 음수의 범위로 간다면 절대 최단 시간이 될 수가 없다.
- 일단 한 번 100,000을 벗어나게 되면 주구장창 -1만 반복해야 함
위 두개의 조건으로 인해 최대 범위는 200,000이 된다는 것을 알 수 있다.
그래서 0 ≤ BFS ≤ 200,000 의 범위에서 BFS를 돌리면 답을 찾을 수 있다. (근데 사실 100,000을 넘어가는 것 자체가 손해임)
why? *2 하고 -1을 n번 하는 것보다 -1하고 *2을 n번 하는게 훨씬 이득임