[백준] 14940번 쉬운 최단거리 (python)

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

14940번: 쉬운 최단거리

 

출력 요구사항을 잘 보면 원래 갈 수 없는 땅인 위치는 0으로 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다. 라고 나와있다. 즉, 목표지점과 0인 부분은 0으로 출력하고, 1이었으나 도달하지 못한 경우에만 -1로 출력하면 된다. 처음에 0인 부분도 -1로 출력해서 틀렸다.

 

문제 해결 방법은 아래와 같다.

 

1. 최단거리를 구하는 것이기 때문에 목표지점부터 시작
   
   • 문제를 처음 읽었을 때 목표 지점은 2로 되어있고, 시작 지점이 명시되어 있지 않아서 출발 지점이 어디지..? 하고 고민했다.
   • 근데 문제를 잘 읽어보면 목표 지점은 유동적이기 때문에 목표 지점을 기준으로 최단 거리를 구하면 된다.
   • 입력받은 지도에서 2를 찾아 큐에 넣어준다.
2. BFS를 이용하여 상하좌우로 탐색
   • 탐색 지점이 1인 경우, 해당 지점에 이전 지점 거리 + 1 을 해서 대입해 준다. 그리고 좌표를 큐에 넣어준다.
   • 탐색 지점이 0인 경우, 방문 여부만 체크해 주고 넘어간다. 지나갈 수 없는 곳이므로 큐에 넣어주지 않는다.
3. 탐색이 끝나면 방문 여부 리스트(visited) 체크
   • 만약 특정 부분이 1인데 방문하지 않았을 경우 -1로 변경해 준다.

 

문제 흐름대로 풀면 되지만, 잘 읽지 않으면 놓칠 수 있는 조건들이 있기 때문에 꼼꼼히 읽고 풀어야 한다.

 

 

정답 코드

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
graph = []
visited = [[False]*m for _ in range(n)]
dq = deque()

for _ in range(n):
    graph.append(list(map(int, input().split())))

for i in range(n):
    for j in range(m):
        if graph[i][j] == 2:
            dq.append([i, j])
            graph[i][j] = 0
            visited[i][j] = True

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

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

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
            if graph[nx][ny] == 1:
                visited[nx][ny] = True
                graph[nx][ny] = graph[x][y] + 1
                dq.append([nx, ny])
            elif graph[nx][ny] == 0:
                visited[nx][ny] = True

for i in range(n):
    for j in range(m):
        if graph[i][j] == 1 and not visited[i][j]:
            graph[i][j] = -1

for i in range(n):
    print(*graph[i])