[백준/BOJ] 2178번 : 미로 탐색 _Python

 

 

 

백준 2178. 미로 탐색 _Python

>접근방법

   토마토 풀었을 때랑 거의 같다. 너비우선탐색 bfs로 인접한 노드로 옮겨갈 때마다 카운트를 누적해 가면서 값을 누적된 카운트 값으로 변경해준다. 그리고 N, M 인덱스의 값을 출력시키면 된다.

 

 

>풀이법

   주석으로 대체

 

 

>코드

import sys
from collections import deque
# 인접노드 탐색용 인덱스
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

# 미로의 최단거리를 구하는 함수
def bfs() :
    while queue:
        a, b = queue.popleft()
		
        # a와 b의 상하좌우 인접한 노드 탐색
        for l in range(4):
            nx, ny = a + dx[l], b + dy[l]

			# 노드가 미로 범위 안이면서 길이 있는 경우(1)
            if 0 <= nx < c and 0 <= ny < r and maze[nx][ny] == 1:
            	# 원래 노드의 값+1을 이동할 노드에 대입
                maze[nx][ny] = maze[a][b] + 1
                # 이동할 노드를 큐에 삽입 -> 위 과정 반복
                queue.append([nx, ny])

## main
# 미로의 세로, 가로 크기 입력받기
c, r = map(int, input().split())
# 미로 정보 입력받기
maze = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(c)]
queue = deque([])

# 시작점에서부터 미로찾기 수행
queue.append([0, 0])
bfs()

# N, M 위치의 값 출력
print(maze[c-1][r-1])

 

 

>결과

 

 

>결론 

토마토 문제랑 너무 비슷해서 날먹했다.

 

2178번: 미로 탐색