[백준/Python] 2178번: 미로탐색 (BFS, 상하좌우 탐색)

1. 문제 

2178번: 미로 탐색

문제를 보고 막막했다. 

지금껏 풀었던 그래프 문제는 주로 방향이 우,하 로 잡혀있었는데 이 문제에서는 상하좌우를 따져주어야했다. 

 

다른 코드를 조금 (많이) 참고했다 ^ ____ ^ .. 

그리구 상하좌우를 탐색하는 방법을 알았다 !! 

 

 

2.  풀이 

 

1) 그래프(미로(0,0))에서 bfs함수를 사용하여 상,하,좌,우 를 모두 검사하고 1인 값을 찾는다

 

2-1 ) 1이라면 그 전 값 +1 

2-2 ) 0이라면 continue 

 

3) 차근차근 모든 미로를 탐색하며 목적지(miros[n-1][m-1])에서 값을 찾을 수 있다 ~ ! 

 

 

 

3. 코드 

# 파이썬 2178

from collections import deque
n,m = map(int,input().split())

miros = []
for _ in range(n):
    miro = list(map(int,input()))
    miros.append(miro)

#확인
# for miro in miros:
#     print(miro)

# 상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x,y):
    queue = deque()
    queue.append((x,y))

    while queue:
        #현재 위치
        x,y = queue.popleft()
        # print('x,y : ',(x,y))

        #현재위치에서 상하좌우 확인
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            # print(nx, ny)

            if nx<0 or nx>=n  or ny<0 or ny>=m:
                continue

            if miros[nx][ny] == 0:
                continue

            if miros[nx][ny] ==1 :
                miros[nx][ny] = miros[x][y] +1

                queue.append((nx,ny))

    # for miro in miros:
    #     print(miro)
    return miros[n-1][m-1]

print(bfs(0,0))

 

 

4 6
101111
101010
101011
111011

이 예제에 대한 miros값은 

 

[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 14]
[4, 5, 6, 0, 14, 15]

 

이렇게 들어간다 ! 
참고로 경로상 재방문을 할 수 있기에 (0,0)값이 3이 나온다 

 

---

🤍 상하좌우 탐색

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
while queue:
    #현재 위치
    x,y = queue.popleft()
    # print('x,y : ',(x,y))

    #현재위치에서 상하좌우 확인
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]

이 부분은 나중에도 유용하게 쓰일것 같으니 꼭꼭씹어먹어봐야겠다 🍴

---

[참고 및 출처] 

https://jokerldg.github.io/algorithm/2021/03/24/maze.html