[프로그래머스] level 3 네트워크 (DFS, BFS)

문제링크

프로그래머스

 

포인트

자기자신은 항상 연결되어 있으며 == 1

상호 연결되어 있는 경우 하나의 네트워크로 취급한다.

 

DFS

package programmers.dfsbfs;

public class NetworkDfsRemind {
    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]){
                dfs(n, i, computers, visited);
                answer++;
            }
        }

        return answer;
    }

    private void dfs(int n, int i, int[][] computers, boolean[] visited) {
        visited[i] = true; //방문 표시

        for(int idx=0; idx<n; idx++){
            if(computers[i][idx] == 1 && !visited[idx]){ //연결 되어있지만 방문 안 한 경우 = 탐색 대상
                dfs(n, idx, computers, visited);
            }
        }
    }


    public static void main(String[] args) {
        /*3    [[1, 1, 0], [1, 1, 0], [0, 0, 1]]    2
          3    [[1, 1, 0], [1, 1, 1], [0, 1, 1]]    1*/
        NetworkDfsRemind n = new NetworkDfsRemind();
        System.out.println(n.solution(3, new int[][]{{1,1,0},{1,1,0},{0,0,1}}));
    }
}

 

BFS

package programmers.dfsbfs;

import java.util.LinkedList;
import java.util.Queue;

//재귀를 통한 bfs 탐색
public class NetworkBfs {

    private static boolean []visited;

    public static void main(String[] args) {
        NetworkBfs n = new NetworkBfs();
        int [][] arr = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}; //간선의 이어짐을 나타냄
        int target = 3; //정점 3개
        System.out.println(n.solution(target, arr));
    }
    public int solution(int target, int[][] computers) {
        int answer = 0;
        //boolean의 default는 false
        visited = new boolean[target];

        for(int idx=0; idx<target; idx++){
            if(!visited[idx]){
                bfs(target, idx, computers);
                answer++;
            }
        }

        return answer;
    }

    private void bfs(int target, int idx, int[][] computers) {
        Queue<Integer> que = new LinkedList<>();
        que.offer(idx); //0
        visited[idx] = true; //0을 true

        while(!que.isEmpty()){
            int temp = que.poll(); // 0을 뺌
            visited[temp] = true; //0을 true
            //{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}
            for(int i=0; i<target; i++){
                if(computers[temp][i] == 1 && !visited[i]){
                    que.offer(i);
                }
            }
        }
    }


}