[백준/Python] 14940. 쉬운 최단거리

📌문제 유형: 그래프 탐색 (BFS)

https://www.acmicpc.net/problem/14940

 

 

 

📌 풀이 

 

전형적인 BFS 문제이다.

 

단, 시작점이 (0,0) 이 아니라 2 값을 갖고 있는 위치부터라는 점! 따라서 먼저 2의 값을 가진 위치를 찾아야 한다. 

 

그 뒤에 모든 지점까지의 최단거리를 출력하라고 한다. 최단거리는 BFS로 구할 수 있다. 

 

이때 움직일 수 있는 방향이 상하좌우이므로, dx/dy를 선언해 bfs() 안에서 for문을 통해 한 지점이 갈 수 있는 상하좌우 4곳을 살펴볼 수 있도록 한다. 이때 갈 수 있는 곳은 queue에 담는다. 

 

여기서 포인트는, 거리 값을 visited에 누적합으로 표현한다는 점이다. 

 

1. 모든 지점에 대해 visited[i][j] = -1로 초기화하고,
2. popleft()한 지점 (x,y) 에 대해 nx/ny (next_x, next_y) 를 찾는다. 
3. 각 nx/ny에 대해 graph 상에서 1이면 갈 수 있으므로, visited[nx][ny] = visited[x][y] + 1로 누적합을 한다. 
4. 각 nx/ny에 대해 graph 상에서 0이면 갈 수 없으므로, visited[nx][ny] = 0으로 둔다. 

 

이를 코드로 표현하면 아래와 같다. 

 

⭐ 그래프 탐색의 기본적인 문제이므로 암기해두자. !

 

from collections import deque
N, M = map(int, input().split())
graph = []
for i in range(N):
    tmp = list(map(int, input().split()))
    # if 2 in tmp:
    #     start = [i, tmp.index(2)]
    graph.append(tmp)

visited = [[-1 for _ in range(M)] for _ in range(N)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def bfs(i, j):
    q = deque()
    q.append((i,j))
    visited[i][j] = 0

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<N and 0<=ny<M and visited[nx][ny] == -1:
                if graph[nx][ny] == 1:
                    q.append((nx, ny))
                    visited[nx][ny] = visited[x][y] + 1
                elif graph[nx][ny] == 0:
                    visited[nx][ny] = 0

# bfs(start[0], start[1])
for i in range(N):
    for j in range(M):
        if graph[i][j] == 2:
            bfs(i, j)

# for i in range(N):
#     print(visited[i])
for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            print(0, end=' ')
        else:
            print(visited[i][j], end=' ')
    print()