[프로그래머스] 네트워크 (Swift)

[프로그래머스] 네트워크 (Swift)

https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

풀이

이차원 배열로 주어진 그래프 정보에서 총 그래프의 개수를 구하는 문제입니다.

 

해당 문제를 풀기 위해서는 한 그래프를 모두 탐색한 다음 그 횟수를 구하면 된다고 생각했습니다. DFS 나 BFS 모두 한번 실행할 시 그래프 전체를 탐색하지만 이번에는 DFS 를 활용해봤습니다.

 

그래프 탐색 여부를 저장하기 위해 먼저 크기가 n 인 visited 배열을 생성합니다. 그리고 반복문을 이용하여 0번 노드부터 탐색을 시작합니다.

 

0번 노드에서 시작한 DFS 가 종료된다면 0번 노드를 포함한 그래프의 visited 는 모두 true 가 되기 때문에 visited 값이 false 인 노드만 찾아 DFS 를 차례로 진행해주면 됩니다.

 

다시 말하자면, visited 의 값이 true 라면 해당 노드를 포함한 그래프는 탐색이 완료된 상태이기 때문에 그렇지 않은 노드들은 아직 탐색이 되지 않은 그래프에 포함된다는 뜻입니다.

 

이렇게 DFS 를 한번 수행할때 마다 그래프의 개수는 1씩 증가하고, 최종적으로 몇개의 그래프를 가지고 있는지 알 수 있습니다.

코드

Swift

 

코드에서 사용된 inout 키워드를 이용하면 파라미터로 전달되는 값을 수정하여 그 결과가 메소드 바깥에서도 유지되게 할 수 있습니다.