알고리즘/자료구조

네트워크

e-pd 2020. 9. 6. 12:54

programmers.co.kr/learn/courses/30/lessons/43162

 

코딩테스트 연습 - 네트워크

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있��

programmers.co.kr

연결여부를 확인하는 문제. 큐에 담아두고 문제를 푼다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;
 
class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[n];
        
        
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            
            answer += 1;
            
            Queue<Integer> queue = new LinkedList();
            queue.offer(i);
            
            while(!queue.isEmpty()) {
                int computer = queue.poll();
                int[] connections = computers[computer];
                
                for (int j = 0; j < connections.length; j++) {
                    if (computer == j) continue; // 자기 자신이면 패스
                    if (visited[j]) continue;
                    if (connections[j] == 1) {
                        visited[j] = true;
                        queue.offer(j);
                    }
                }
            }
        }
        
        return answer;
    }
}
 cs

 

stack의 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;
 
class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[n];
        
        
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            
            answer += 1;
            
            Stack<Integer> stack = new Stack();
            stack.push(i);
            
            while(!stack.isEmpty()) {
                int computer = stack.pop();
                int[] connections = computers[computer];
                
                for (int j = 0; j < connections.length; j++) {
                    if (computer == j) continue; // 자기 자신이면 패스
                    if (visited[j]) continue;
                    if (connections[j] == 1) {
                        visited[j] = true;
                        stack.push(j);
                    }
                }
            }
        }
        
        return answer;
    }
}
cs