백준 14940 쉬운 최단거리(Python) - BFS

🖥️문제 링크

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

14940번: 쉬운 최단거리

🎀해결 방법

queue를 사용해서 BFS로 시작했다

1. queue 생성

2. 시작점 찾아서 queue에 넣기 + 0인 부분 표시하기

3. 방향 바꿔가면서 범위, 이동 가능여부 확인 후 queue에 넣기

큰 형식은 이렇게 생각하고 문제를 풀었다

 

🐸직면한 문제

1. 닿지 못하는 부분은 -1로 처리 (문제 잘 읽기,,🤣)

2. arr에서 벽에 막힌 부분이 1로 표시되는 문제

3. n, m 을 반대로 쓴 문제..

 

두번째 문제에서는

마지막에 -1로 바꿔서 출력할 수 있었지만, 출발점에서 1인 경우와 겹칠 수 있어서

기존에 -1로 채워놓았던 visited에 벽을 표시하고, 거리를 기록하는 방식으로 수정해서

문제를 해결할 수 있었다

 

예제가 한 개뿐이라서 틀린 이유를 어려웠다. 그래서 여러 반례를 테스트 해봤는데,

혹시 이 반례들이 다 맞는 경우라면 꼭 기본적인 n, m 같은 코드를 확인해야 한다

🐯반례

 

#input
3 3
2 0 1
0 1 1
1 1 1
    
#anser
0 0 -1
0 -1 -1
-1 -1 -1

#input
2 2
2 0
0 0

#answer
0 0
0 0

 

✨BFS - 정답 코드

from collections import deque
n,m = map(int,input().split())
queue = deque([])
arr = [] 
visited = [[-1]*m for _ in range(n)]        # 기존에 만든 visited

for i in range(n):
    li = list(map(int, input().split(' ')))
    for j in range(m):
        if li[j] == 2:
            queue.append((i,j))
            visited[i][j] = 0
        elif li[j] == 0:                    # 벽인 경우는 visited에도 0으로 표시
            visited[i][j] = 0 
    arr.append(li)

direc = [(0,1),(1,0),(0,-1),(-1,0)]

while queue:
    (x,y) = queue.popleft()
    for d in direc:
        nx, ny = x + d[0], y + d[1]
        if 0 <= nx < n and 0 <= ny < m:
            if visited[nx][ny] == -1 and arr[nx][ny] == 1:
                queue.append((nx,ny))
                visited[nx][ny] = visited[x][y] + 1
                arr[nx][ny] = 0             # 입력 받았던 arr에 지나간 표시 

for i in visited:
    print(*i)