[SWEA][D4] - Ladder1(1210번)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh 

SW Expert Academy

이 문제는 처음에는 금방 풀 수 있을 줄 알았다.
분명 내가 생각한 로직이 맞다고 생각했는데, 이상하게 해결이 되지 않았고, 어렵다고 생각했다.

막상 해결하고 난 지금 다시 문제를 보니 굉장히 사소한 부분에서 걸렸었다.

먼저 나는 이 문제를 지난시간 풀이했던, 백준의 안전영역 문제와 단지번호 붙이기와 같은 DFS 탐색 알고리즘으로 해결하려고 했다.

그리고 내가 원하는 목적지로 갈 수 있는 출발지를 찾는 문제이기에 두가지 방식을 떠올렸다.

1. 출발할 수 있는 모든 출발지에서 일단 출발하고 나서 어디에 도착하는지를 보고, 내가 원하는 목적지에 도달하는 출발지를 출력한다.

2. 거꾸로 목적지에서 출발지를 향해 사다리를 타고 올라가 해당 목적지로 온 출발지를 찾는다.

당연히 2번 방식이 더 쉽고, 대부분 이렇게 푼다.
하지만 1번도 도전하고 싶었다.

내가 이 문제를 풀다 난관에 봉착했던 점이 두가지가 있었다.

첫번째는 방문 배열 초기화이다.

위의 코드를 보면 4번째 줄 DFS 위에 Reset으로 방문 배열을 초기화해주는 것을 볼 수 있다.
물론 Reset함수를 만들지 말고 new로 방문 배열을 초기화 해주어도 상관없다.
처음에는 어차피 테스트 케이스가 달라질때 new가 선언되면서 초기화가 진행되니 문제 없다고 생각했지만
사다리의 특성장 모든 사다리가 연결되어 있어, 첫 출발지에서 사다리까 끝날때까지 DFS돌며 생성된 visited 배열을 초기화 시켜주지 않으면, 두번째 출발지에서 내려가다가 첫번째 출발지에서 만들어진 visited 배열 때문에 탐색을 할 수가 없어 정답을 도출할 수 없다.

따라서 한 출발지에서 사다리 끝까지 내려갔으면 다음 출발지에서 출발하기 전에 반드시 방문배열을 초기화해주어야 한다.

위는 코드는 초기화를 진행하는 함수이다. new로 새로 생성하며 초기화해도 되지만 명시적으로 작성해보았다.

두번째는 재귀함수 탈출하는 기저조건 선정이다.

위 코드를 보면 사다리를 끝까지 내려왔을때 목적지가 내가 원하는 목적지가 아니더라도 return으로 끝을 내야한다.
이 부분을 해주지 않아 자꾸 출력값이 0이 나왔다.

아래는 전체 코드와 깃허브 주소이다.

1. 출발할 수 있는 모든 출발지에서 일단 출발하고 나서 어디에 도착하는지를 보고, 내가 원하는 목적지에 도달하는 출발지를 출력한다.

2. 거꾸로 목적지에서 출발지를 향해 사다리를 타고 올라가 해당 목적지로 온 출발지를 찾는다.

https://github.com/Headfish96/Online-Judge

GitHub - Headfish96/Online-Judge: This is a auto push repository for Baekjoon Online Judge created with [BaekjoonHub](https://gi