[lv.3] 네트워크

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

• 문제
  

• 풀이
  1) 각 노드에 대한 check 배열 생성 후 for문
  2) check가 되지 않은 노드일 경우 bfs/dfs
  3) computers[now][i]가 1이고, i가 체크되지 않을 경우에 큐에 넣거나 dfs(i)를 돌린다.

• 소감
  사실 원래 쓰려던 코드가 있었으나 틀렸다.

import java.util.*;

class Solution {
    static boolean[][] check;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int mx;
    static int my;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        mx = computers.length;
        my = computers[0].length;
        check = new boolean[mx][my];
        for(int i=0; i<mx; i++){
            for(int j=0; j<my; j++){
                if(!check[i][j] && computers[i][j]==1){
                    answer++;
                    bfs(i, j, computers);
                }
            }
        }
        return answer;
    }
    public void bfs(int i, int j, int[][] graph){
        Queue<int[]> queue = new LinkedList<>();
        check[i][j] = true;
        queue.add(new int[]{i, j});
        while(!queue.isEmpty()){
            int[] now = queue.poll();
            for(int a=0; a<4; a++){
                int nx = now[0]+dx[a];
                int ny = now[1]+dy[a];
                if(nx<0 || ny<0 || nx>=mx || ny>=my) continue;
                if(check[nx][ny] || graph[nx][ny]==0) continue;
                queue.add(new int[]{nx, ny});
                check[nx][ny] = true;
            }
        }
    }
}

지도형으로 생각한 뒤 2중 for문을 돌려 상하좌우로 연결이 되어있지 않음에 따라 접근할려 했으나 반례가 존재하였다.

1 0 1    -> 0~2가 전부 연결된 상태이기에 1이 나와야 함
0 1 1
1 1 1

즉, 위의 그래프는 양방향 그래프이지만 위에서 사용한 코드는 단방향 그래프에서 사용하는 코드이기에 맞지 않은 코드였다.

• 코드 (BFS)

import java.util.*;

class Solution {
    static boolean[] check;
    public int solution(int n, int[][] computers) {
        int answer = 0;        
        check = new boolean[n];
        for(int i=0; i<n; i++){
            if(!check[i]){
                answer++;
                bfs(computers, i, n);
            }
        }
        return answer;
    }
    public void bfs(int[][] graph, int start, int n){
        Queue<Integer> queue = new LinkedList<>();
        check[start] = true;
        queue.add(start);
        while(!queue.isEmpty()){
            int now = queue.poll();
            for(int i=0; i<n; i++){
                if(graph[now][i]==1 && !check[i]){
                    check[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}

• 코드 (DFS)

import java.util.*;

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

• BFS vs DFS
  BFS : 최단 경로, 다음에 방문할 곳을 큐에 담아서 메모리를 잡아먹음
  DFS : 최단 경로 불가, 해가 없는 경로에 깊이 빠지면 시간 낭비, 깊은 단계의 해를 더 빨리 찾음, 내부적으로 스택 이용