[알고리즘] 백준 2606번

[알고리즘] 백준 2606번

문제

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

---

풀이

오늘도 BFS/DFS 문제를 풀어보았습니다. 사실 지금까지 BFS로만 풀어서 DFS에 대한 감을 잃을까봐 이번 문제는 DFS로 풀어보았습니다. 재귀를 이용하여 풀었는데 간만에 DFS로 시도했더니 머리가 잘 돌아가지 않는 것을 느꼈습니다. 그래서 실수도 많았고 시간도 오래걸렸습니다. 사실 로직 자체는 크게 어렵지 않았습니다. 하지만 사소한 문제들과 제가 생각하지 못한 반례가 있어서 그 부분에 대해 언급하고자 합니다.

제가 생각한 풀이 과정은 다음과 같습니다.

1. 시작점(1)을 시작으로 재귀를 이용한 DFS를 사용해야겠다고 생각했습니다.
2. 배열을 사용하자니 낭비되는 메모리가 많은 것 같아서 List와 ArrayList를 사용했습니다. 이 때문에 코드가 약간 지저분해진 것도 없지 않아 있습니다. 제가 아직은 자바에 익숙하지 않기 때문인 것 같습니다.
3. 방문을 했거나 더는 연결된 노드가 없다면 백트래킹을 해서 돌아가야 했습니다.

다음은 저의 코드입니다.

사실 크게 이해하기 힘든 부분이 있는 코드는 아닙니다. 하지만 저는 한가지를 생각하지 못해 상당히 오랜 시간을 소모했습니다. 그것은 바로 양방향에 대한 것을 고려해주지 않았기 때문입니다. 처음부터 그것에 대해 생각을 안한 것은 아닙니다. 하지만 단방향으로 구현해도 크게 다를 것이 없다고 생각한 아주 초보적인 안일함 때문이였습니다. 반례를 예를 들어보도록 하겠습니다.

 3
 2
 1 3
 2 3

 3
 2
 1 3
 2 3

위와 같은 입력이 들어가게 되면 양방향을 고려해주지 않았기 때문에 원하는 출력 결과인 2가 나오지 않습니다. 그렇기 때문에 위의 코드에서 1번과 2번 주석과 같이 양방향을 고려해준 코드를 작성하여 문제를 해결하였습니다.

---

오늘의 배운점

그래프에 대한 알고리즘을 고려할 때는 양방향성도 염두에 두어야 한다.