[백준] #14940 쉬운 최단거리 (python)

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

문제 설계

#2의 위치 (x,y) 구함

#2의 위치를 시작으로 bfs

#maps 배열 만들고

#visited=[[-1]*m for _ in range(n)] 로해서 visited[x][y]=0으로 놓고 시작

 

문제 풀이

틀린 풀이

from collections import deque

n,m=map(int,input().split())
maps=[]

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

for i in range(n):
    row=list(map(int,input().split()))
    maps.append(row)
    if 2 in row:
        x=i
        y=row.index(2)

visited=[[-1]*m for _ in range(n)]
q=deque()
q.append((x,y))
visited[x][y]=0

while q:
    x,y=q.popleft()
    for k in range(4):
        nx,ny=x+dx[k],y+dy[k]
        if 0<=nx<n and 0<=ny<m and maps[nx][ny]==1 and visited[nx][ny]==-1:
            visited[nx][ny]=visited[x][y]+1
            q.append((nx,ny))
        elif 0<=nx<n and 0<=ny<m and maps[nx][ny]==0 and visited[nx][ny]==-1:
            visited[nx][ny]=0
for row in visited:
    print(*row)

 

 

정답

from collections import deque

n,m=map(int,input().split())
maps=[]

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

for i in range(n):
    row=list(map(int,input().split()))
    maps.append(row)
    if 2 in row:
        x=i
        y=row.index(2)

visited=[[-1]*m for _ in range(n)]
q=deque()
q.append((x,y))
visited[x][y]=0

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

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

    print()

 

정리

처음엔 이렇게 생각했다:

어차피 벽도 0이고, 거리 0도 0이니까,
visited만 써서 출력해도 상관없는 거 아닌가?

실제로 여러 예제를 돌려보면 정답 출력이 잘 나오기도 한다.

 

하지만, 이 방식의 한계는?

❗ 의미 구분 불가능

visited[i][j] == 0인 경우:

• 그 칸이 벽(0)이었는지
• 출발점이었는지
• 정말 거리 0으로 도달한 칸인지
  → 단순히 visited만 보면 구분이 불가능하다.

내가 구현한 방식은 visited만 사용해서 출력하지만, 문제 조건에서는 전혀 문제없다.

하지만 visited에 0이라는 값이 여러 의미(벽, 출발점, 거리 0)를 동시에 가질 수 있어 출력에 신중해야 한다.

maps까지 함께 고려하면 명확하고 확장성 있는 출력이 가능하다.

즉, 현재 문제에서는 정답이지만, 일반화나 습관을 생각한다면 maps + visited로 출력하는 습관이 더 안전하다.