[Java] 프로그래머스_43162 : 네트워크

깊이 우선 탐색(DFS)

네트워크 - Level3

 

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

프로그래머스

 

 

 

 

풀이

import java.util.*;

class Solution {
    
    private void visitAll(int computer, int[][] computers, boolean[] isVisited) {
        Stack<Integer> s = new Stack<>();
        s.push(computer);
        
        while (!s.isEmpty()) {
            int idx = s.pop();
            
            if (isVisited[idx]) continue;
            isVisited[idx] = true;
            
            for (int next = 0; next < computers[idx].length; next++) {
                if (computers[idx][next] == 0) continue;
                s.push(next);
                System.out.println(s);
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        boolean[] isVisited = new boolean[n];
        int answer = 0;
        
        for (int i = 0; i < n; i++) {
            if (isVisited[i]) continue;
            visitAll(i, computers, isVisited);
            answer++;
        }
        
        return answer;
    }
}

 

 

 

 

n = 3
computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]

 

이는 3개의 컴퓨터가 존재하며, 1번 컴퓨터와 2번 컴퓨터가 서로 연결되어 있고, 3번 컴퓨터는 독립적으로 존재한다는 것을 의미한다.

1. 초기 상태:
   • isVisited: [false, false, false]
   • answer: 0
2. solution 메서드 호출:
   • visitAll(0, computers, isVisited) 호출
     • 현재 컴퓨터: 0
     • DFS를 통해 연결된 컴퓨터들을 방문
     • 1번과 2번 컴퓨터가 연결되어 있으므로 두 컴퓨터를 방문하고 isVisited를 업데이트: [true, true, false]
   • answer를 1 증가: 1
3. visitAll(1, computers, isVisited) 호출
   • 현재 컴퓨터: 1
   • 이미 방문한 1번 컴퓨터이므로 넘어감
   • DFS를 통해 연결된 컴퓨터들을 방문
   • 아무런 방문 없음
4. visitAll(2, computers, isVisited) 호출
   • 현재 컴퓨터: 2
   • 3번 컴퓨터가 독립적으로 존재하므로 3번 컴퓨터를 방문하고 isVisited를 업데이트: [true, true, true]
   • answer를 1 증가: 2

최종적으로 answer는 2가 되어야 한다. 이는 서로 연결된 1번과 2번 컴퓨터 그룹, 그리고 독립적인 3번 컴퓨터로 이루어진 두 개의 그룹이 존재함을 나타낸다.

 

 

n = 3
computers = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]

 

이는 3개의 컴퓨터가 존재하며, 1번 컴퓨터와 2번 컴퓨터가 서로 연결되어 있고, 3번 컴퓨터는 독립적으로 존재한다는 것을 의미한다.

1. 초기 상태:
   • isVisited: [false, false, false]
   • answer: 0
2. solution 메서드 호출
   • visitAll(0, computers, isVisited) 호출
     • 현재 컴퓨터: 0
     • DFS를 통해 연결된 컴퓨터들을 방문
     • 1번과 2번 컴퓨터가 연결되어 있으므로 두 컴퓨터를 방문하고 isVisited를 업데이트: [true, true, false]
     • answer를 1 증가: 1
3. visitAll(1, computers, isVisited) 호출
   • 현재 컴퓨터: 1
   • 이미 방문한 1번 컴퓨터이므로 넘어감
   • DFS를 통해 연결된 컴퓨터들을 방문
     • 2번 컴퓨터가 3번 컴퓨터와 연결되어 있으므로 3번 컴퓨터를 방문하고 isVisited를 업데이트: [true, true, true]
     • answer를 1 증가: 2
4. visitAll(2, computers, isVisited) 호출
   • 현재 컴퓨터: 2
   • 이미 방문한 2번 컴퓨터이므로 넘어감
   • DFS를 통해 연결된 컴퓨터들을 방문
   • 아무런 방문 없음

최종적으로 answer는 2가 되어야 한다. 이는 모든 컴퓨터들이 연결되어 있어 하나의 그룹을 형성하고 있음을 나타낸다.

 

 

 

해당 문제를 풀면서 문제를 분석하는데도 쉽지 않았다. 역시 Level3 문제는 나에게 아직 어렵다...!

하지만 직접 그림을 그려가면서 생각해보니 문제를 해석할 수 있었다.

그리고 출력문을 이용하는 것도 잊지 말자! 문제를 풀어나가는 데에 많은 도움이 되었다!