[Lv3] 네트워크

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다.

예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고,

컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때

컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다.

따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때,

네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

 

입출력 예 설명

예제 #1

아래와 같이 2개의 네트워크가 있습니다.

예제 #2

아래와 같이 1개의 네트워크가 있습니다.

 

---

 

자기 자신은 항상 1로 표시됩니다.

 

[1,0,0,1,0]

[0,1,0,0,0]

[0,0,1,1,0]

[1,0,0,1,0]

[0,0,0,0,1]

 

여기서 정답은 3개입니다.

 

1번과 4번이 이어져 있는걸 1,4에서 직접 확인할 수 있는데,

3번과 4번도 이어져 있는걸 3에서만 확인할 수 있습니다.

 

결국 1,3,4가 하나의 네트워크라는 건데, 이처럼 모든 정보가 명확히 표기되어있진 않아서 정보를 합쳐야합니다.

 

 

네트워크 정보를 하나 꺼내서, 거기에 적힌 애들을 데려와서 합치고.. 다시 완성된 정보로 또 합치고.. 는 만드는 제가 길을 잃을 것 같네요.

 

DFS로 뜀뛰기를 할 생각입니다.

 

위의 예시라면, 5칸의 방문정보 [X,X,X,X,X]를 두고,

 

 

처음에 1번 방문했으니, [O,X,X,X,X],

 

1번에서 4번에 대한 정보를 얻고, 4번 가면서, [O,X,X,O,X], (1은 자기자신)

 

4번에서 3번에 대한 정보를 얻고, 3번 가면서, [O,X,O,O,X]. (그리고 4는 이미 방문)

 

번져갈 정보가 없으니, 방문정보 [O,X,O,O,X] 중 방문 안했던 2로 가면서, [O,O,O,O,X].

 

번져갈 정보가 없으니, 방문정보 [O,O,O,O,X] 중 방문 안했던 5로 가면서, [O,O,O,O,O].

 

이제 더 방문할 데가 없음. 이렇게 3덩이의 네트워크가 있음.

 

public void dfs(int[][] computers, boolean[] check, int index) {
    check[index] = true;
    for(int i=0;i<computers[index].length;i++) {
        if(i!=index && computers[index][i]==1 && !check[i]) {
            dfs(computers, check, i);
        }
    }
}

public int solution(int n, int[][] computers) {
    boolean[] check = new boolean[computers.length];
    int answer = 0;
    for(int i=0;i<computers.length;i++) {
        if(!check[i]) {
            answer++;
            dfs(computers, check, i);
        }
    }
    return answer;
}

 

boolean[] 배열로 방문정보를 두고, 처음칸부터 시작하여 방문하면서, 시작할 때가 되면 answer++.