[백준🥈1] #14940 쉬운 최단거리 (Python)

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

14940번: 쉬운 최단거리

 

문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

예제 입력 1

15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

예제 출력 1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

 

✔️ Code

from collections import deque

def bfs(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    visited[x][y] = 1
    graph[x][y] = 0
    queue = deque()
    queue.append((x, y))

    while queue:
        x, y = queue.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < n and 0 <= ny <m and graph[nx][ny] == 1 and visited[nx][ny] == 0:
                visited[nx][ny] = 1
                queue.append((nx, ny))
                graph[nx][ny] = graph[x][y] + 1

n, m = map(int, input().split())
x, y = 0, 0

visited = [[0 for _ in range(m)] for _ in range(n)]
graph = []

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

for i in range(n):
    for j in range(m):
        if graph[i][j] == 2:
            x, y = i, j
            break

bfs(x, y)

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

for i in graph:
    for j in i:
        print(j, end = ' ')
    print()

 

✏️ Comment

풀면서 2가지 걸림돌(?)이 있었다.
1. graph[i][j] == 2 일 때 graph[i][j] = 0 으로 바꾸고 bfs 함수를 돌렸더니 bfs를 돌면서 graph[nx][ny]가 2로 바뀐 값들도 0으로 바뀌는 문제
해결) graph[i][j] == 2인 인덱스를 따로 x, y라는 변수에 저장을 해준 뒤, break로 for문을 빠져나온 후에 bfs(x,y)를 수행해서 graph[x][y] = 0으로 바꿔줌으로써 해당 문제를 해결했다.

2. 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1로 출력해주어야 하는데 깜빡하고 그 부분을 처리하지 않음
해결) bfs 함수를 다 돌고난 뒤의 graph를 확인해서 visited[i][j] == 0 and graph[i][j] == 1인 원소들은 값을 -1로 바꿔주었다.
원래 갈 수 있는 땅의 값이 1인데, 도달하지 못했다면 bfs 함수를 다 끝낸 이후에도 여전히 1일 것이고, 도달 여부의 판별은 visited를 통해서 알 수 있기 때문에 위와 같은 조건문을 통해 해결했다. 

코드가 많이 지저분하고 비효율적인 면도 있는 것 같아서 다른 풀이들 참고하면서 다시 풀어볼 예정이다!