Today I Learned

오늘은 DFS 문제를 풀어봤다.

네트워크 (DFS 문제)

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

• 문제
  컴퓨터(노드)가 직간접적으로 연결 된 것을 네트워크라 정의하고 네트워크의 수를 파악하는 문제. 총 컴퓨터 수 n과 연결정보가 2차원 인접배열로 제시된다. 단, 인접배열은 n번 컴퓨터가 배열안에선 n-1의 위치로 취급된다.

• 구현과정
  문제를 보자 마자 기본적인 DFS 문제라고 생각했다.
  한 네트워크를 DFS로 끝까지 들어가면서 순회하고, 순회가 완료되면 다음 네트워크로 넘어가면서 answer(네트워크의 개수)를 1씩 늘리면 풀리는 문제라고 생각했다.단, 주의해야할 것은 간선 정보가 2차원 배열에서 0번째 인덱스를 비워놓지 않아 n번 노드가 index (n-1)로 표현되니 헷갈릴 수 있어 조심해야 했다.

• 최종 코드

import java.util.*;
class Solution {
    private static boolean[] visited; // 방문 체크용 boolean 배열
    private static int answer;
    
    private void dfs(int v, int[][] computers){
        visited[v-1] = true; // 방문처리
        for(int i=0; i<visited.length; i++){
        	// 아직 방문하지 않았고 간선정보에서 1로 연결되어있는 컴퓨터를 재귀로 방문
            if(!visited[i] && computers[v-1][i]==1){
                dfs(i+1, computers);
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        answer = 0;
        visited = new boolean[n]; // computers처럼 0번 안비우려고 n개만 만듬
        for(int i = 0; i<n; i++){ // 1과 0으로 간선정보가 왔기때문에 그냥 for문 씀
            if(!visited[i]) {	// index i 가 방문안했으면 i+1번 컴퓨터 dfs방
            
                dfs(i+1, computers);
                answer++; // 네트워크 하나를 다 순회했으므로 개수를 1씩 증가
            }
        }
        return answer;
    }
}

• 보완사항?
  answer를 dfs 안에서 쓸 줄 알고 static으로 필드에 선언해뒀는데 그냥 main 메서드에서만 썼다. 지우는게 나을듯..
  오히려 computers를 main에서 바로 받아서 전역처리하는게 더 깔끔할뻔
  간단한 기본문제라 나중에 딱히 리팩토링을 안해도 될정도로 구현이 간단하게 나왔다.