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

Algorithm

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

김디니 2023. 1. 27. 14:29

문제

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

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

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

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

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

input =
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

output =
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

전체 코드

from collections import deque

# 세로, 가로
n, m = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
queue = deque()

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

for i in range(n):
    for j in range(m):
        
        # 목표 지점을 찾은 후 목표지점부터 탐색 시작
        if maps[i][j] == 2:
            queue.append((i, j))
            
            while queue:
                x, y = queue.popleft()
                
                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    
                    if 0 <= nx < n and 0 <= ny < m:
                        if maps[nx][ny] == 1 and visited[nx][ny] == 0:
                            visited[nx][ny] = visited[x][y] + 1
                            queue.append((nx, ny))


for k in range(n):
    for b in range(m):
        if maps[k][b] == 1:
            if visited[k][b] == 0:
                visited[k][b] = -1  # 도달하지 못한 좌표는 -1로 표시한다.
                
for i in visited:
    print(*i)

문제 풀이 포인트

BFS
- 4방향 탐색
방문 리스트로 목표지점과의 거리를 표시한다.

로직

좌표에 있는 목표지점(2)을 찾는다.
목표지점의 좌표를 deque에 넣어준다.
목표지점을 시작으로 4방향을 탐색하며 더 나아갈 수록 좌표값에 1씩 더해준다.
도달하지 못한 지점은 -1로 표시한다.
for문으로 방문리스트를 하나씩 출력한다.

코드 디테일

목표지점을 찾은 후 4방향 탐색

목표지점 찾기

for i in range(n):
    for j in range(m):
        
        if maps[i][j] == 2:
            queue.append((i, j))

이중 for문으로 좌표값이 2인 좌표를 찾아 queue에 넣어준다.

4방향 탐색하기

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

BFS방식으로 dx, dy에 저장한 4방향으로 탐색하며

방문한 좌표의 값이 1일 경우 방문하고 현재 위치(visited[x][y]) 좌표값에 1을 더해준다.

예를 들어,

3 3
1 1 2
1 1 1
1 1 1

이러한 입력값이 주어졌을 때

이중 for문으로 2의 위치가 maps[0][2]임을 찾아내고 maps[0][2]을 시작지점으로 4방향 탐색을 시작한다.

목표지점인 2를 기준으로 떨어져 있는 거리 측정은 방문 리스트에 기록하도록 한다.

4방향 탐색을 통해 1인 좌표값은 queue에 저장되고 x, y 값에 하나씩 할당하게 되는데,

이때 탐색한 좌표값이 1인 경우 현재 위치의 좌표값에 1씩 더해주므로 거리값이 나오게 되는 것이다.

도달하지 못한 지점 -1로 표시

for k in range(n):
    for b in range(m):
        if maps[k][b] == 1:
            if visited[k][b] == 0:
                visited[k][b] = -1

위 과정 후 좌표값이 1이지만 4방향 탐색으로 도달하지 못한 지점은

이중 for문으로 탐색 후 -1로 표시한다.

정답 출력

for i in visited:
    print(*i)

for문으로 리스트 형식을 제외한 데이터를 출력하기 위해 *를 사용하여 정답을 출력한다.