파이썬) 쉬운 최단거리 - BOJ

 

https://www.acmicpc.net/problem/14940

 

import sys
input = sys.stdin.readline

from collections import deque
N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
visited = [[-1] * M for _ in range(N)]
dx, dy = [0,0,-1,1], [-1,1,0,0]

def bfs(i,j):
    queue = deque()
    queue.append((i,j))

    visited[i][j] = 0

    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            
            if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == -1:
                if graph[nx][ny] == 0: 
                    visited[nx][ny] = 0
                elif graph[nx][ny] == 1:
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx,ny))

for i in range(N):
    for j in range(M):
        if graph[i][j] == 2 and visited[i][j] == -1:
            bfs(i,j)

for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            print(0, end=' ')
        else:
            print(visited[i][j], end=' ')
    print()

제목처럼 그렇게 쉽지는 않았다.

테스트케이스가 워낙 적어 뭐가 틀렸는지 찾느라 결국 해결하지 못했다.

아래는 내가 제출한 코드이다.

from collections import deque
import sys

n, m = map(int, input().split())

arr = [list(map(int, input().split())) for _ in range(n)]

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


visit = [[False for _ in range(m)]for _ in range(n)]


q = deque()


for i in range(n):
    l = list(map(int, input().split()))

    for j in range(len(l)):
        if l[j] == 2:
            l[j] = 0
            visit[i][j] = True
            q.append((i, j))

    arr.append(l)
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


while q:
    x, y = q.popleft()

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m:
            if visit[nx][ny] == False:
                if arr[nx][ny] == 1:
                    q.append((nx, ny))
                    arr[nx][ny] = arr[x][y] + 1
                    visit[nx][ny] = True

for i in range(len(arr)):
    for j in range(len(arr)):
        if visit[i][j] == False and arr[i][j] != 0:
            print(-1, end=' ')
        else:
            print(arr[i][j], end=' ')
    print()
for i in arr:
    print(' '.join(map(str, i)))

다시봐도 뭐가 틀렸는지 모르겠다...ㅠㅠ