백준 11724: 연결요소의 갯수 (Swift)

BFS문제중에서는 신박한 문제였던 것 같다.

뿐만 아니라, DFS, BFS 또는 union-find 알고리즘으로 각 노드의 parent를 체크하고, Set()자료형을 이용해 마무리할 수도 있는 문제이다.

출제자 의도대로 BFS로 풀이해보았다.

 

각 노드를 모두 나타낼 수 있도록 n+1크기만큼의 visited배열을 만들어놓은 후,

30 번째 줄부터, 1번 ~ n번 노드를 모두 돌며,

 

1. visited여부가 false인 노드가 나타나면,

2. 해당 노드의 visited = true로 설정해주고

3. 해당 node를 출발 node로 하여 bfs함수를 호출하여, 연결된 모든 node의 visited를 true로 바꿔준다

4. 이렇게 반복문에서 visited가 false인 node를 만날 때마다 count를 1 증가시켜주어

5. 최종적으로 count를 리턴해준다.

 

bfs()함수는 아래의 dfs()함수로 대체할 수 있다.