가중치
-
[DFS/BFS] 문제 이름 : 미로 탈출Algorithm/유형별 문제 풀기 2021. 7. 8. 11:34
문제 설명 N x M 크기의 직사각형의 미로가 주어질 때, 주인공의 위치는 (1,1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸식 이동할 수 있다. 이때 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시되는데, 이때 주인공이 미로를 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 1. 사용 알고리즘 그래프 탐색 - BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 2. 문제 해결 아이디어 주어진 문제는 미로를 탈출하기 위한 최소 칸의 개수를 구하는 것이므로, 탐색 시 더 이상 길이 없다면 다시 되돌아오게 되고 그러면 이때까지 잘못된 길로 갔을 때의 이동횟수..