[Silver I] 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

---

# 풀이 방법

1. 시작위치인 ‘2’를 찾는다
2. 시작위치로부터 다른 지점과의 거리를 dist배열에 담는다

---

# 코드

# 2025-05-18 10:30 - 11:05
from collections import deque
import sys
sys.stdin = open("input.txt","r")
n, m = map(int,sys.stdin.readline().split())
grid = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
dist = [[-1] * m for _ in range(n)]

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

def bfs(x,y):  
    queue = deque()
    queue.append((x,y))
    dist[x][y] = 0  # 시작점은 거리 0
    
    while queue:
        x,y = queue.popleft()

        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if 0 <= nx < n and 0 <= ny < m:
                if grid[nx][ny] in (1,2) and dist[nx][ny] == -1:
                    dist[nx][ny] = dist[x][y] + 1
                    queue.append((nx,ny))
    
    return 0

# 시작 지점 찾기 (값이 2인 곳)
for i in range(n):
    for j in range(m):
        if grid[i][j] == 2:
            bfs(i, j)

for i in range(n):
    for j in range(m):
        if grid[i][j] == 0:
            print(0, end = ' ')
        else:
            print(dist[i][j], end = ' ')
    print()

 

---

# 참고

처음에 왜 이런식으로 풀었지..? 2 지점을 먼저 찾았어야 했다

# 2025-05-18 10:30 -11:03 
from collections import deque
import sys
# sys.stdin = open("input.txt","r")
n, m = map(int,sys.stdin.readline().split())
grid = [[0]*m for _ in range(n)]
for i in range(n):
    grid[i] = list(map(int,sys.stdin.readline().split()))


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

def bfs(x,y):
    # 갈 수 없는 땅인 경우
    if grid[x][y] == 0:
        return 0
    
    visited = [[False]*m for _ in range(n)]
    queue = deque()
    queue.append((x,y,0))
    visited[x][y] = True
    
    while queue:
        x,y,cnt = queue.popleft()

        if grid[x][y] == 2:
            return cnt

        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if 0 <= nx < n and 0 <= ny < m:
                if grid[nx][ny] in (1,2) and not visited[nx][ny]:
                    visited[nx][ny] = True
                    queue.append((nx,ny,cnt+1))
    
    return 0


for i in range(n):
    for j in range(m):
        cnt = bfs(i,j)
        print(cnt, end = ' ')
    print()