13913 숨바꼭질 4 (BFS 역추적)

https://www.acmicpc.net/problem/13913

1.접근

bfs역추적을 방문했던곳인지 확인하는 check배열을 만들어  바로 전 값을 저장하도록 해서 추적하게 했다.

2.풀이

출발지점에서 도착지점까지 가는 +1,-1,*2의 3가지 뿌리로 bfs를 만들어준다. 여기서 방문했던 곳인지 확인하는 check 배열을 -1로 초기화 시킨다.bfs를 통하여 방문할때마다 cnt대신에 자신의 바로 전 위치를 집어 넣어주면 -1도 아니게 되고 어떤 경로로 현재 지점에 와있는지 알 수 있게된다.

따라서 큐에서 도착지점 값이 나올 때 cnt값을 반환하고 도착지점에서부터 시작지점까지 check배열을 순서대로 거꾸로 따라가보면 어느 경로로 왔는지 나온다.(마지막 while 문)

3.코드

4.배운점

• 처음에 check배열에 cnt값을 넣는게 습관화되어서 역추적을 할 때 함수를 또 만들어서 bfs를 돌리느라 시간과 코드가 커졌다, check배열에 바로 전의 값을 넣어주면 추적하기 쉬워지는걸 배웠다.
• DSLR문제도 11779번 최소비용 구하기 다익스트라 문제도 내 바로 전 상태를 기록하고 싶다면 방문했던곳인지 확인하는 배열에 바로 전 값을 넣어서 풀면 쉽게 풀린다.
• 역추적은 전체 걸린 횟수와 관련이 많은 것 같다.