14940번 쉬운 최단거리

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

---

풀이

너무 BFS 문제였다.
값이 2인 시작 위치를 찾고 여기를 기준으로 BFS 돌면서 거리를 계산하면 된다.
유의할 점은 원래 값이 0이면 0이 출력되어야 한다.

그래서 -1로 초기화된 nXm visited 2차원 리스트를 만들고 마지막에 출력할 때 값이 0이면 visited 값을 0으로 바꿨다.

for i in range(n):
    for j in range(m):
        if graph[i][j] == 0: # 갈 수 없는 땅이면
            visited[i][j] = 0
        print(visited[i][j], end=" ")
    print()

1. 시작 위치 찾는 함수를 만들어서 값이 2인 위치를 찾고 리턴. 이때 시작 위치의 visited 값은 0을 넣어준다.
(사실 이건 bfs 함수 내에서 해도 되는데 기능 분리하는 함수 있으면 좋을 것 같아서 써봤다.)

# 시작 위치 찾기
def start():
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 2: # 시작 위치
                visited[i][j] = 0
                return i, j

2. bfs 함수를 만들어서 시작 위치 기준으로 상하좌우 거리 계산하기(현재 자기 visited 인덱스 + 1 하면 됨)

def bfs(R, C):
    queue.append((R, C))
    while queue:
        r, c = queue.popleft()

        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]

            if nr < 0 or nr >= n or nc < 0 or nc >= m: continue  # 범위 밖

            if visited[nr][nc] == -1 and graph[nr][nc] != 0:
                visited[nr][nc] = visited[r][c] + 1
                queue.append((nr, nc))

---

코드

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

queue = deque()

# 시작 위치 찾기
def start():
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 2: # 시작 위치
                visited[i][j] = 0
                return i, j


def bfs(R, C):
    queue.append((R, C))
    while queue:
        r, c = queue.popleft()

        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]

            if nr < 0 or nr >= n or nc < 0 or nc >= m: continue  # 범위 밖

            if visited[nr][nc] == -1 and graph[nr][nc] != 0:
                visited[nr][nc] = visited[r][c] + 1
                queue.append((nr, nc))


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

dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

R, C = start() # 시작 위치
bfs(R, C)

for i in range(n):
    for j in range(m):
        if graph[i][j] == 0: # 갈 수 없는 땅이면
            visited[i][j] = 0
        print(visited[i][j], end=" ")
    print()