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

그래프, bfs / 실버 1

🗺️

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

14940번: 쉬운 최단거리

 

내 풀이

from collections import deque

def bfs(x, y):
    q = deque()
    q.append((x,y))

    while q:
        cx, cy = q.popleft()

        for k in range(4):
            nx, ny = cx + dx[k], cy + dy[k]

            if 0 <= nx < n and 0 <= ny < m and ans[nx][ny] == -1: # 범위를 벗어나지 않고, 방문하지 않은 경우
                if land[nx][ny] == 1: # 이동할 수 있는 땅인 경우
                    ans[nx][ny] = ans[cx][cy] + 1 # 이전 값에 +1
                    q.append((nx, ny))

n, m = map(int, input().split())
land = [[] * m for _ in range(n)]
ans = [[-1] * m for _ in range(n)]

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

for i in range(n):
    land[i] = list(map(int, input().split()))

for i in range(n):
    for j in range(m):
        if land[i][j] == 0:
            ans[i][j] = 0
        elif land[i][j] == 2:
            # 목표 지점 좌표
            targetX = i
            targetY = j

ans[targetX][targetY] = 0
bfs(targetX, targetY)

for i in range(len(ans)):
    print(*ans[i])

bfs(너비 우선 탐색)으로 풀었다.

 

 

코드 설명

 

ans: 정답 리스트

전체 리스트를 -1로 초기화했다. 

-1은 방문하지 않은 땅임을 의미한다.

후에 해당 땅을 방문하게 되면 양의 정수로 대체될 것이고, 도달할 수 없는 위치인 경우에는 -1이 그대로 유지될 것이다. 

ans = [[-1] * m for _ in range(n)]

 

가로와 세로로만 움직일 수 있다 ➡ 상하좌우로 이동할 좌표를 리스트에 저장해야 한다.

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

 

모든 땅을 돌면서 방문할 수 없는 땅과 목표 지점을 알아냈다.

방문할 수 없는 땅을 만났다면, 정답 리스트에도 똑같이 반영해야 한다.

for i in range(n):
    for j in range(m):
        if land[i][j] == 0:
            ans[i][j] = 0
        elif land[i][j] == 2:
            # 목표 지점 좌표
            targetX = i
            targetY = j

 

목표 지점의 좌표에서는 목표 지점까지의 거리가 0이기 때문에 0으로 치환한다.

목표 지점의 좌표를 매개변수로 넣어 bfs를 호출한다.

ans[targetX][targetY] = 0
bfs(targetX, targetY)

 

 

✔️ bfs 함수 내

 

범위를 벗어나지 않고, 방문하지 않은 땅인 경우이며, 이동할 수 있는 땅인 경우라면

이전 값에 1을 더해준 뒤(거리를 1 증가시킨 뒤), deque에 좌표를 추가한다.

if 0 <= nx < n and 0 <= ny < m and ans[nx][ny] == -1: # 범위를 벗어나지 않고, 방문하지 않은 경우
    if land[nx][ny] == 1: # 이동할 수 있는 땅인 경우
        ans[nx][ny] = ans[cx][cy] + 1 # 이전 값에 +1
        q.append((nx, ny))

 

 

어려웠던 점

 

갈 수 없는 땅(0)을 다루는 과정에서 난항이 있었다.

처음에는 다음과 같이 bfs 함수 내에서 이동할 수 있는 땅인 경우와 이동할 수 없는 땅인 경우를 나누어 함께 처리했었는데,

틀렸다.

if 0 <= nx < n and 0 <= ny < m and ans[nx][ny] == -1: # 범위를 벗어나지 않고, 방문하지 않은 경우
    if land[nx][ny] == 1: # 이동할 수 있는 땅인 경우
        ans[nx][ny] = ans[cx][cy] + 1 # 이전 값에 +1
        q.append((nx, ny))
        
    # 처음에 처리했던 방식
    elif land[nx][ny] == 0: # 이동할 수 없는 땅인 경우
        ans[nx][ny] = 0

 

위의 코드를 살펴보면,

이동할 수 있는 땅인 경우에만 deque에 좌표를 추가해주고 있다.

즉, 이동할 수 없는 땅에서는 상하좌우로 이동할 기회가 주어지지 않는다는 것이다. 

다음과 같이 이동할 수 없는 땅이 한 겹인 경우에는 문제가 발생하지 않는다.

 

문제가 발생하는 케이스는, 다음과 같이 이동할 수 없는 땅이 여러 겹으로 주어졌을 때이다.

 

이동할 수 없는 땅인 0에서는 상하좌우로 이동할 기회가 주어지지 않기 때문에,

노란색 박스의 값들이 검사되지 않고 함수가 종료되게 된다.

 

따라서 이동할 수 없는 땅을 정답 리스트에 똑같이 반영해주는 과정을 먼저 수행하고 나서 bfs를 호출해야 한다!

 

뭐가 잘못됐는지 모르겠어서, 구글링 해볼까하다가 조금 더 생각해 보고 결국 스스로 해결했다. 뿌듯 ✌🏻