[BOJ] 14940번 쉬운 최단거리

[BOJ] 14940번 쉬운 최단거리 문제

약간의 변형이 들어간 BFS(Breadth First Search) 문제다. 다만 어디까지나 약간의 변형이므로 BFS 처리에 집중하는 것이 중요하다.

---

이 문제는 누가 봐도 BFS라는 것을 알 수 있다. 하나뿐인 시작 지점인 2를 찾고, 그 지점에서 BFS를 돌리면서 닿는 구간마다 1을 더해주면 된다.

본인은 여기서 약간의 변형인 "1인 지점이지만 갈 수 없는 곳이라면 -1을 출력한다"에서 실수를 저지르고 말았다. 문제를 끝까지 읽어야 겠다는 생각만 든다...

---

import sys
from collections import deque

def bfs(I, J, N, M):
    visited = [[False for _ in range(M)] for _ in range(N)]
    dist = [[0 for _ in range(M)] for _ in range(N)]
    travel = deque([[I, J]])
    di, dj = [1, -1, 0, 0], [0, 0, 1, -1]
    while travel:
        now_i, now_j = travel.popleft()
        if visited[now_i][now_j]:
            continue
        visited[now_i][now_j] = True
        for i in range(4):
            next_i, next_j = now_i+di[i], now_j+dj[i]
            if 0 <= next_i < N and 0 <= next_j < M and not visited[next_i][next_j]:
                if graph[next_i][next_j] == 1:
                    travel.append([next_i, next_j])
                    if dist[next_i][next_j] == 0:
                        dist[next_i][next_j] = dist[now_i][now_j] + 1

    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1 and dist[i][j] == 0:
                dist[i][j] = -1

    for now_dist in dist:
        print(*now_dist)

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().rstrip().split())
    graph = list()
    for _ in range(n):
        graph.append(list(map(int, sys.stdin.readline().rstrip().split())))

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 2:
                bfs(i, j, n, m)
                exit()

 

코드에서의 어려움은 크게 없다.

입력을 받고, 2인 곳을 찾는 즉시 BFS를 돌려서 거리를 구하고, 1이지만 BFS로 돌지 못했다면 그 부분만 -1로 바꿔준 후 BFS 최종 결과를 출력하고 종료하면 된다.