-
[Python] 백준 - 2178 미로 탐색__Python/__Algorithm 2022. 1. 7. 16:24
# 실버 1
[문제]
링크 : https://www.acmicpc.net/problem/2178
문제 풀이
- 그래프탐색
- BFS
- 최단 경로를 찾아야하기 때문에, DFS는 불가
- 갈림길이 있을 경우, 최단 경로를 어떻게 판단할지 고민
- 처음에는 길이 막혔을 경우, 되돌아오도록 짬 => 실패(출구까지 막힌 길이 없을 경우)
- 기본 BFS, 미로 진입 시 cnt =1부터 다음 진행할 때마다 cnt + 1으로 갱신 => 1번과 같은 사유로 실패(cnt값이 엄청나게 커짐)
- 최종) 2번 변형, 다음 진행방향의 cnt 값을 현재 위치값의 +1로 갱신
구현 코드
import sys def bfs(i,j): from collections import deque visited[i][j] = 1 q = deque([[i,j]]) while q: x,y = q.popleft() dx = [-1,1,0,0] dy = [0,0,-1,1] for i in range(4): nx = x + dx[i] ny = y + dy[i] if (0 <= nx < N) and (0 <= ny < M): if (maze[nx][ny] == 1) and (visited[nx][ny] == 0): q.append([nx,ny]) visited[nx][ny] += visited[x][y] +1 N,M = map(int, sys.stdin.readline().split()) maze = [list(map(int,sys.stdin.readline().rstrip())) for _ in range(N)] visited = [[0] * M for _ in range(N)] bfs(0,0) print(visited[N-1][M-1])
실행 결과
728x90'__Python > __Algorithm' 카테고리의 다른 글
[Python] 백준 - 2667 단지번호 붙이기 (0) 2022.01.07 [Python] 백준 - 9020 골드바흐의 추측 (0) 2022.01.07 [Python] 백준 - 1904 01타일 (0) 2021.12.21 [Python] 백준 - 9184 신나는 함수 실행 (0) 2021.12.21 [Python] 백준 - 1003 피보나치 함수 (0) 2021.12.21