백준 14940번: 쉬운 최단거리 (S1) - Python 풀이

문제 설명

https://www.acmicpc.net/problem/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

풀이 과정

2가 적힌 지점에서 1이 적힌 지점까지 얼마나 걸리는지 탐색하면 됩니다.

상하좌우의 거리가 모두 1로 동일하기 때문에 다익스트라는 안 써도 되고 BFS로 최단거리를 탐색합니다.

1이 적힌 지점인데도 도달할 수 없는 위치가 발생하는 예시는 아래와 같습니다.

3 3 2 1 1 0 0 0 1 1 1

0 0 0이 막고 있어서 2에서 맨 아래칸 1 3개까지는 도달할 수 없습니다.

이는 visited 변수를 통해 판단할 수 있습니다. 보드에는 1이 적혀 있는데 BFS 탐색 후에도 visited 값이 False라면 2에서 도달할 수 없는 1이기 때문에 해당 부분은 -1로 적어주는 작업이 필요합니다.

정답 코드

from collections import deque

n, m = map(int, input().split())
board = [[] for _ in range(n)]
visited = [[False for _ in range(m)] for _ in range(n)]

x = 0
y = 0
for i in range(n):
    board[i] = list(map(int, input().split()))

# 시작지점의 x,y값 찾았는지 여부
is_founded = False
# 보드를 탐색하며 시작지점의 x,y 값을 찾는다
for i in range(n):
    for j in range(m):
        # 보드에 2가 적혀 있다면 그곳이 시작지점의 위치
        if board[i][j] == 2:
            # 이때의 x,y값 저장
            x, y = i, j
            is_founded = True
            break
    # for문 탈출
    if is_founded:
        break

# 상하좌우 이동을 위한 방향 벡터
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 시작지점 x,y에서 각 좌표까지의 최단거리 찾기
def BFS(x, y):
    # deque에 좌표를 튜플 형식으로 저장
    q = deque([(x, y, 0)])
    # 방문 처리
    visited[x][y] = True
    # 보드에는 이동거리를 적는다 즉, 자기자신까지는 거리가 0이니까 0을 넣은 것
    board[x][y] = 0

    # 큐가 빌 때까지 반복
    while q:
        # 큐에서 값 꺼냄
        now_x, now_y = q.popleft()
	      
        # 상하좌우 좌표 확인
        for d in range(4):
            nx = now_x + dx[d]
            ny = now_y + dy[d]
            # 유효 범위에 있고 아직 방문되지 않았고 보드에 적힌 값이 0이 아니면
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and board[nx][ny] != 0:
                # 큐에 해당 좌표 (nx, ny)를 push
                q.append((nx, ny))
                # 방문 처리
                visited[nx][ny] = True
                # 현재까지의 이동거리에 +1한 값으로 (nx, ny) 위치의 보드 값을 업데이트 
                board[nx][ny] = board[now_x][now_y]+1

# 2에서 각 좌표까지의 최단거리 찾기
BFS(x, y)

# 2에서 도달할 수 없는 1이 있을 때 -1로 처리
for i in range(n):
    for j in range(m):
        if not visited[i][j] and board[i][j] != 0:
            board[i][j] = -1

# 언패킹을 통해 배열을 간단히 출력
for i in range(n):
    print(*board[i])

이상입니다.