백준 6416번 트리인가?

문제링크: https://www.acmicpc.net/problem/6416

사용한 알고리즘: DFS(?)


트리인지 아닌지 판단하는 문제였습니다. 트리는 root 가 하나여야 하고, root를 제외한 나머지 모든 node 들의 indegree ( 해당 node 로 들어오는 edge 의 개수 ) 가 1 이어야합니다.

문제 풀이는 다음과 같습니다.
(1) node 들이 1,2,3,4, ... 등으로 순서대로 들어오는 게 아니기 때문에 tree를 구성하는 노드들이 입력되면 이를 set으로 저장합니다.

(2) 각 입력 a, b 를 받으면서 벡터 배열로 a 의 자식이 b가 있음을 저장하고, 다른 int 배열을 만들어 b의 indegree++ 을 해줍니다.

(3) 우선 set으로 모은 모든 점들의 indegree들을 보면서 indegree 가 0 인 점, 즉 root 가 단 한개 인지, 다른 모든 점들의 indegree 는 모두 1 인지 확인해줍니다.

(4) 과정 (3)에서 구한 root 를 시작으로 DFS 를 돌려줍니다. DFS 를 돌릴때는 root를 시작으로 모든 자식들을 다시 DFS 함수로 넣어주는 식으로 진행됩니다. 이때 방문하게 되는 자식들을 체크해주어, root에서 시작하여 모든 점들을 단 1회 방문하는지 확인해줍니다.

과정 (4)가 필요한 이유를 반례를 들어 설명드리면,
root 가 1이고 1->2, 1->3 인 점 3개로 구성된 tree 하나와, 서로 edge가 있는 두점 4,5, 즉 4->5, 5->4 인 두 점이 입력으로 주어지면, 과정 (1)~(3)으로는 이 경우가 tree가 맞다고 판단하게 됩니다. 따라서 root에서 각 점을 1회 방문하는지 확인해 주어야 합니다.