[BOJ] 백준 4803 트리 (Swift)

문제

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

4803번: 트리

풀이

무방향 그래프에서 사이클이 있는 지 판별해야 하는 문제입니다.
여러 방법이 있겠지만 저는 DFS를 사용하였습니다.

무방향 그래프이기 때문에 1번 노드와 2번 노드가 연결되어 있다면, 1 -> 2, 2 -> 1 로 가능하기에 사이클이 존재한다고 할 수 있지만,
이러한 점을 제외하기 위해서, 직전의 노드로 탐색하는 것은 제외하고 이미 방문한 노드를 또 방문한다면 사이클이 있다고 판별해주었습니다.

소스코드

후기

처음에는 DFS 함수에서 이미 방문한 노드를 또 방문할 때, 바로 false를 리턴하도록 구현했습니다.
계속해서 오답판정을 받아서 왜 그런지 확인을 해봤는데,

다음과 같을 때, 1번 노드부터 DFS를 실행하면 3번 노드에서 1번 노드를 방문할 때 이미 방문한 노드이므로 false를 리턴하고 DFS 함수를 종료하게 됩니다.
그렇다면 4번 노드는 아직 방문하지 않았기 때문에, 4번 노드에 대해 DFS를 한 번 더 수행하는게 이상했습니다.

결론적으로 이어저 있는 그래프를 전부 방문을 하지 않고 return을 하는 것에 대해서 문제가 있었기에 따로 변수를 두어 전부 방문처리를 한 후,
트리인지 아닌지 확인해주도록 구현하여 정답 판정을 받았습니다.