프로그래머스 '네트워크' 자바

 

이 문제는 dfs로 풀어야 되겠다는 감은 왔다

그래서 처음엔 이런 그림을 상상에 두고 코드를 짰다

 

package codingtestStudy;

public class Network {
    int n = 9;
    int [][] computers = {{1, 1, 0, 0, 0, 0, 0, 0, 0},
                          {1, 1, 0, 1, 1, 0, 0, 0, 0},
                          {0, 0, 1, 0, 1, 0, 1, 0, 0},
                          {0, 1, 0, 1, 0, 1, 0, 0, 0},
                          {0, 0, 0, 0, 1, 0, 0, 0, 0},
                          {0, 0, 0, 1, 0, 1, 0, 0, 0},
                          {0, 0, 1, 0, 0, 0, 1, 0, 0},
                          {0, 0, 0, 0, 0, 0, 0, 1, 1},
                          {0, 0, 0, 0, 0, 0, 0, 1, 1}};

    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[n];

        for(int i = 0; i < n; i++){
            System.out.println(visited[i]);
            if(visited[i] == false){
                dfs(computers, i, i, visited);
                answer++;
            }
            System.out.println("현재 네트워크 수는 " + answer);
        }
        return answer;
    }

    public static void main(String[] args) {
        Network nw = new Network();
       int answer = nw.solution(nw.n, nw.computers);
        System.out.println("정답은 " + answer);
    }

    void dfs(int[][] computers, int x, int y, boolean[] visited){
        //방문한 노드 처리
        visited[x] = true;

        for(int i = y; i < computers.length; i++){
            if(x != i && visited[i] == false && computers[x][i] == 1 ){
                System.out.println("현재 노드는 " + i);
                dfs(computers, i, i, visited);
            }
        }
    }
}

이 코드는 테스트 코드는 다 통과했고 내가 그려놓은 위 이미지의 코드도 통과했다. 하지만 실제로 테스트 케이스를 돌려보면 실패가 떴는데 그 이유는 for문의 시작을 y로 고정해버리니 더 작은 수의 부모 노드를 탐색할 수 없었다   

    void dfs(int[][] computers, int x, int y, boolean[] visited){
        //방문한 노드 처리
        visited[x] = true;

        for(int i = 0; i < computers.length; i++){
            if(x != i && visited[i] == false && computers[x][i] == 1 ){
                System.out.println("현재 노드는 " + i);
                dfs(computers, i, i, visited);
            }
        }
    }
}

그래서 for문을 그냥 0부터 시작하게 됐더니 통과 됐다(살짝 허무)

처음부터 이렇게 안 짠 이유는 어차피 더 큰 수의 노드까지 가는 동안 연결된 나머지 노드들은 다 탐색 됐을꺼라고 생각해 시간을 줄여보고자 그렇게 했었는데 위 그림과 같은 경우를 생각 못했다.

어설프게 시간 줄이려고 코드 짜지 말고 예외의 경우도 항상 생각하자