[프로그래머스] 네트워크 (JAVA)

프로그래머스

 

풀이

 

1. 문제 풀이 아이디어

배열에 ArrayList넣어서 각 노드별로 연결되어있는 노드들의 목록을 만들었다(이중포문 전체를 돌지 않아도 되어 효율적이라 생각했음) 처음 문제를 보자마자 덩어리가 몇 개인지 구해야하기 때문에 DFS로 문제를 해결했다. BFS로도 풀 수 있다고 들어 BFS로도 문제를 풀어봤음.

 

2. 배열에 ArrayList 넣는 법

// ArrayList를 배열로 생성
ArrayList<Integer>[] arr = new ArrayList[N+1];

// 각 배열마다 ArrayList 생성
for(int i=0;i<=N;i++){
	arr[i] = new ArrayList<>();
}

// 배열에 값 넣는 방법
for(int i=0;i<M;i++){
	st = new StringTokenizer(br.readLine());
	int A = Integer.parseInt(st.nextToken());
	int B = Integer.parseInt(st.nextToken());
	arr[B].add(A);
}

출처: https://abcodef.tistory.com/25 [abc의 다락방:티스토리]

 

 

3. 다른 사람들은 어떻게 풀었는가

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] chk = new boolean[n];
        for(int i = 0; i < n; i++) {
            if(!chk[i]) {
                dfs(computers, chk, i);
                answer++;
            }
        }
        return answer;
    }
    void dfs(int[][] computers, boolean[] chk, int start) {
        chk[start] = true;
        for(int i = 0; i < computers.length; i++) {
            if(computers[start][i] == 1 && !chk[i]) {
                dfs(computers, chk, i);
            }
        }
    }
}

 

내가 생각한 것처럼 방문해야할 노드만 찾아준 것이 dfs내의 코드인 것 같다.

0에서 n까지의 노드중 방문하지 않은 경우, for문을 돌면서 다음 방문해야할 노드(아직 방문하지 않은)를 찾아다닌다.

 

 

전체코드

 

DFS풀이

import java.io.*;
import java.util.*;

class Solution {
    static ArrayList<Integer>[] network;
    static boolean[] visited;
    static int answer = 0;
    public int solution(int n, int[][] computers) {
        network = new ArrayList[computers.length];
        visited = new boolean[computers.length];
        
        //각 컴퓨터와 연결되어 있는 컴퓨터 목록을 network에 넣기
        for(int i=0; i<computers.length; i++){
            network[i] = new ArrayList<>();
            for(int j=0; j<computers[i].length; j++){
                if(computers[i][j] == 1){
                    network[i].add(j);
                }
            }
        }
        
        for(int i=0; i<computers.length; i++){
            if(!visited[i]){
                visited[i] = true;
                DFS(i);
                answer++;
            }
        }
        return answer;
    }
    static void DFS(int node){
        for(int i=0; i<network[node].size(); i++){
            int next = network[node].get(i);
            if(!visited[next]){
                visited[next] = true;
                DFS(next);
            }else{
                continue;
            }
        }
    }
}

 

BFS풀이

import java.io.*;
import java.util.*;

class Solution {
    static ArrayList<Integer>[] network;
    static boolean[] visited;
    static int answer = 0;
    public int solution(int n, int[][] computers) {
        network = new ArrayList[computers.length];
        visited = new boolean[computers.length];
        
        //각 컴퓨터와 연결되어 있는 컴퓨터 목록을 network에 넣기
        for(int i=0; i<computers.length; i++){
            network[i] = new ArrayList<>();
            for(int j=0; j<computers[i].length; j++){
                if(computers[i][j] == 1){
                    network[i].add(j);
                }
            }
        }
        
        for(int i=0; i<computers.length; i++){
            if(!visited[i]){
                visited[i] = true;
                BFS(i);
                answer++;
            }
        }
        return answer;
    }
    
    static void BFS(int node){
        Queue<Integer> q = new LinkedList<>();
        q.offer(node);
        
        while(!q.isEmpty()){
            int now = q.poll();
            for(int i=0; i<network[now].size(); i++){
                int next = network[now].get(i);
                if(!visited[next]){
                    visited[next] = true;
                    q.offer(next);
                }
            }
        }
    }
}