174291   2년 전

제목 그대로

도착점까지 가는 길을 찾아서 칸 수를 출력하기는 하는데
그 길이 최단경로가 아닙니다.

코드는 대강 이런 구조로 짰습니다


0.cnt를 한 번 센다
1. 현재 있는 방이 도착점인지 확인
 1-1. 맞다면 지금까지 센 cnt를 큐에 추가
 (단 큐에 들어있는 cnt보다 작을 때만)
2. 아니라면 오른쪽, 아래쪽, 위쪽,아래쪽을 탐색
3. 탐색한 방 중 뚫려있고(값이1),아직 방문하지 않은 방을 시작점으로 다시 탐색


아무래도 제 생각에는,
도착점까지 가는 경로들이 겹치는 경우가 있는데,
미방문 처리된 방만 탐색한다는 조건 때문에
모든 경로들이 제대로 탐색이 안되는 것 같습니다

그러니까 예를들어
A경로에서 도착점까지 [1][1]방을 거쳐갔고,
B경로에서도 [1][1]방을 거쳐야 하는데
A경로에서 거치면서 방문 처리가 되어버려서
해당 방을 가지 못하고 막힌 것으로 인식하는 것 같습니다


어떻게 풀어야할지 모르겠는데 좀 봐주시면 감사하겠습니다 ! (코드가 좀 지저분해서 죄송합니다)

djm03178   2년 전

이 문제는 BFS로 푸는 문제이고, BFS를 하는 데에 재귀 호출은 필요하지 않습니다. BFS의 개념을 공부한 후에 다시 풀어보세요.

댓글을 작성하려면 로그인해야 합니다.