[ 백준 2178 - 미로탐색 ] - bf

 

---

 

• 단위벡터 사용하여 상하좌우 이동하기

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

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

 

• bfs를 어떻게 사용하여 최단 경로를 도출하는가?

- queue 자료구조 자체가 일단 최단 경로를 뽑아내는 데에 사용된다.

- 이를 어떻게 사용하는가 함은 '이동하는 곳 = 이전 위치의 수 + 1'

- 이동할 때마다 1씩 수가 증가될 것이다 = 거리의 수

- queue와 popleft를 이용하여 이동이 진행되기 때문에 자연스레 목표 지점에는 최단 거리의 수가 구해질 것 

def bfs(x,y): 

...
..

    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= 0 and nx <= 가로 and ny >= 0 and ny <= 세로:
                if graph[nx][ny] == 1:
                    graph[nx][ny] = graph[x][y] + 1
                    queue.append((nx,ny))

 

• 방문 체크는 어떻게 이루어지나?

- 이동한 지점의 값이 1이다 = 아직 방문하지 않은 곳

- 이동한 지점의 값이 1이 아니다 = 방문했던 곳

 

왜 1인지 아닌지로 판단하나?

- 이동했던 곳은 전부 거리만큼 수가 더해져있도록 코드를 짜놨기 때문