알고리즘 | BFS 활용하여 미로 찾기 문제 풀기

 

백준 2178번 미로탐색

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

2178번: 미로 탐색

 

 

n = 4
m = 6

graph = [
	[1, 0, 1, 1, 1, 1],
 	[1, 0, 1, 0, 1, 0],
 	[1, 0, 1, 0, 1, 1],
 	[1, 1, 1, 0, 1, 1]
 ]

 

0과 1로 이루어진 n * m 크기의 미로 그래프가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

 

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

 

먼저 상하좌우로 움직일수 있는 x, y 델타값을 리스트로 작성한다.

def dfs_escape(start = (0, 0)):
	# x, y의 현재 포지션을 정해 준다. 
    x_pos = start[0]
    y_pos = start[1]
    
    # 할 일을 기록할 디큐 리스트 q를 작성한다.
    q = deque()
    
    # 가장 처음 초기값을 세팅해준다. x, y의 좌표값 위치를 튜플로 집어넣는다.
    q.append((x_pos, y_pos))
    
    # 할 일이 없을 때까지 반복!
    while q:
    	now_x, now_y = q.popleft()
        
        # 상하좌우 4번 반복
        for i in range(4):
        	next_x = now_x + dx[i]
        	next_y = now_y + dy[i]
            
            # 만약 다음으로 갈 좌표값이 미로를 벗어나지 않는다면
            if 0 <= next_x < n and 0 <= next_y < m:
                if graph[next_x][next_y] == 1:
                    graph[next_x][next_y] = graph[now_x][now_y] + 1
                    q.append((next_x, next_y))

 

bfs_miro()


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


graph[n-1][m-1]
# 15