백준 파이썬 14940번 쉬운 최단거리 (Today I Learn 2025.01.22)

백준 파이썬 공부 2025.01.22
14940번 쉬운 최단거리 (실버 1)

1. 문제
지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

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

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

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

4. 문제 풀이
최단 거리를 구하는 문제이므로 BFS를 사용하여 문제를 해결해 보았다.

>>>코드 1. 틀렸습니다.

import sys
from collections import deque

def BFS():    
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    while queue:
        y, x = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
        
            if 0 <= nx < m and 0 <= ny < n and visited[ny][nx] == 0:
                if graph[ny][nx] == 1:
                    visited[ny][nx] = visited[y][x] + 1
                    queue.append((ny, nx))
                elif graph[ny][nx] == 0:
                    visited[ny][nx] = -1
    
n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]

for i in range(n):
    for j in range(m):
        if graph[i][j] == 2:
            start_y, start_x = i, j

queue = deque([(start_y, start_x)])
BFS()

for i in range(n):
    print(*visited[i])

뭐가 틀렸지 계속 찾아봤는데 아예 못가는 위치는 -1이 아니라 0이고,
갈 수 있는 땅 중에 못가는 위치가 -1이 나오는 거였다.

>>>코드 2. 정답

import sys
from collections import deque

def BFS():    
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    while queue:
        y, x = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
        
            if 0 <= nx < m and 0 <= ny < n and visited[ny][nx] == 0:
                if graph[ny][nx] == 1:
                    visited[ny][nx] = visited[y][x] + 1
                    queue.append((ny, nx))
    
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1 and visited[i][j] == 0:
                visited[i][j] = -1
    
n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]

for i in range(n):
    for j in range(m):
        if graph[i][j] == 2:
            start_y, start_x = i, j

queue = deque([(start_y, start_x)])
BFS()

for i in range(n):
    print(*visited[i])

5. 문제 링크
https://www.acmicpc.net/problem/14940