[알고리즘] 백준 11403번

[알고리즘] 백준 11403번

문제

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

---

풀이

사실 이 문제의 제목만 보고 풀만하겠다는 생각을 했습니다. 이미 정답률 39퍼센트의 BFS문제도 풀었기 때문에 자신감이 넘쳤습니다. 하지만 역시 쉽게 풀지는 못했습니다. 그래도!! 어떻게 보면 제가 처음부터 끝까지 힌트도 얻지 않고 스스로 푼 문제는 이것이 처음인 것 같습니다! 그래서 상당히 뿌듯했고 답을 제출할 때는 모니터 앞에서 맞췄습니다! 라는 문구가 뜨기까지 굉장히 초조하게 지켜보았습니다.

저의 풀이과정은 다음과 같습니다.

1. 저는 먼저 그래프를 그려서 확인해보았습니다. 먼저 출발점에서 갈 수 있는 모든 점을 찾아야 하기 때문입니다.
2. 예제 입력에서 볼 수 있다시피 0은 1로 연결되어 있고 1은 2로 연결되어 있습니다. 마지막으로 2는 0으로 연결되어 있기 때문에 최종적으로 0은 1 과 2 그리고 다시 0으로 돌아올 수 있습니다. 그러므로 예제 출력에서 첫번째 줄이 1 1 1이 나오는 것입니다.
3. 저는 각 점에서 모두 BFS 탐색하기로 하였습니다.

1. 각 점들을 모두 BFS 탐색을 해주었습니다.
2. 시작점에서 경우를 모두 한번씩만 탐색하기 위해 방문한 점은 다시 방문하지 않습니다.
3. 예제 입력을 예를 들어 설명해보자면 0을 시작점으로 BFS탐색을 할 때 0에서 1로는 갈 수 있기 때문에 reuslt[0][1]는1로 체크합니다. 그리고 여기서 1은 큐로 들어가고 1에서 갈 수 있는 점을 다시 검사합니다. 그렇게 되면 1에서 갈 수 있는 점은 현재 이 루프가 0을 시작점으로 하였기 때문에 0에서 갈 수 있는 점이 됩니다. 다시 정리하자면 0에서 1을 갈 수 있고 1에서 2로 갈 수 있으니 0에서 2로 갈 수 있는 것입니다. 0 --> 1 + 1 --> 2 =0 --> 2