[프로그래머스] Lv.3 네트워크 (DFS/BFS, Java)

 

문제설명

입력 & 출력

 

나의 풀이

 

컴퓨터의 개수 N과 각 컴퓨터 간의 연결 상태를 나타내는 2차원 배열 computers가 주어질 때 서로 연결된 컴퓨터들을 하나의 네트워크로 간주하고 전체 네트워크의 개수를 리턴하는 문제입니다.

 

해당 문제는 DFS로 연결된 노드들을 쉽게 찾을 수 있습니다.

 

먼저 Solution에서는 입력으로 주어지는 컴퓨터의 개수 n과 연결에 대한 정보 배열인 computers를 인자로 받습니다.

 

입력받은 컴퓨터의 개수만큼 노드가 있어야 하기 때문에 n만큼의 크기를 가지는 visited배열을 초기화를 해줍니다.

 

연결된 네트워크의 개수를 0으로 초기화해주고, 모든 노드들을 순회하는 반복문을 선언합니다.

 

만약 해당 노드가 아직 방문하지 않은 노드라면, dfs를 수행하여 해당 네트워크의 모든 노드를 방문처리해 줍니다.

 

dfs함수를 나오면 연결된 모든 노드들을 순회하고 나오는데 만약 연결되어있지 않은 노드를 만난다면 해당 네트워크는 다른 네트워크이기 때문에 네트워크의 개수 cnt변수를 증가시켜 줍니다.

 

그리고 DFS함수에서는 인자로 받은 노드를 방문처리해 주고, 인자로 받은 노드와 연결된 다른 노드들을 순회합니다.

 

만약 아직 방문하지 않은 노드이면서 해당 노드가 다른 노드와 연결되어 있다면 (1) dfs함수를 재귀호출 하여 연결된 네트워크를 모두 방문해 줍니다.