1189 컴백홈

1189 컴백홈 / c++ / Silver1 / 18분

문제 및 코드

풀이 과정

그래프 / 깊이 우선 탐색

1. R x C 크기의 보드에 갈 수 있는 곳 ‘.’ 과 갈 수 없는 곳 ‘T’가 주어질 때, 좌하단에서 우상단까지의 거리가 K인 가짓수를 출력하는 문제
2. 최단 거리를 찾는게 아니다보니, 너비우선탐색보다 깊이우선탐색으로 진행했다.
3. 길의 상태인 Board와, 해당 칸까지의 거리를 기록한 Cost를 참고하여, 방문하지 않은 곳 중 갈 수 있는 곳이라면 이전칸까지의 거리 + 1로 거리를 갱신하고, 재귀적으로 DFS를 진행
4. DFS 진행 중, 현재 칸이 0, C-1 (우상단) 칸이고, 현재 칸 까지의 거리가 K-1 (시작지점을 0으로 잡았기 때문에) 라면 Answer에 1을 더해준다.
5. DFS가 종료된 후 Answer를 출력
6. 해결

다시 생각해 볼 점

1. 깊이 우선 탐색만 할 줄 안다면 쉽게 풀 수 있는 문제였다.