반응형
https://www.acmicpc.net/problem/2178
미로 탐색 문제
미로를 탐색해 나갔을 때, 도착 지점에 도착할 경우 총 몇 칸을 이동하게 되는지 구하는 문제
BFS를 활용하면 간단하게 풀 수 있는 문제
내가 푼 정답코드
def finding(a,b): #길을 찾아주자
visited = [[0]* M for _ in range(N)]
queue = [[a,b]]
visited[a][b] = 1 # 방문 처리
while queue:
y, x = queue.pop(0)
for dy, dx in move:
ny, nx = y + dy, x + dx
if 0 <= ny < N and 0 <= nx < M and visited[ny][nx] == 0 and maze[ny][nx] != 0:
visited[ny][nx] = visited[y][x] + 1 # 출발지부터 이동한 거리재기
queue.append([ny,nx])
return visited[N-1][M-1] #도착점 도착했을 때 거리
import sys
N, M = map(int, sys.stdin.readline().split())
maze = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
move = [[1,0],[-1,0],[0,1],[0,-1]]
print(finding(0,0)) #출발 지점
가장 기본이 되는 BFS를 이용한 미로를 탐색하는 문제이다.
접근 법은 BFS를 구현해주고, 다음칸이 이동할 수 있는 인접 칸이면 다음칸에 현재칸 +1한 만큼 이어 나가면 도착 지점에 도착할 때까지 이동한 거리를 알 수 있다.
느낀 점
BFS를 활용한 미로 탐색의 가장 기본이 되는 문제이다. 이전에 미로 탐색 문제를 여러번 풀어봐서 큰 어려움 없이 풀 수 있었다.
반응형
'알고리즘 풀이 > 백준' 카테고리의 다른 글
[백준 7569] 토마토 (python) (0) | 2023.03.04 |
---|---|
[백준 7576] 토마토 (python) (0) | 2023.03.04 |
[백준 1012] 유기농 배추(python) (0) | 2023.03.03 |
[백준 10431] 줄 세우기(python) (0) | 2023.03.02 |
[백준 2615] 오목 (python) (0) | 2023.03.02 |
댓글