바이러스

바이러스

백준 바이러스 문제이다.

인접리스트와 Queue를 활용한 BFS풀이

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.sql.SQLOutput;  
import java.util.*;  
  
class Main {  
    static int [] vis;  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
  
        int N = Integer.parseInt(br.readLine());  
  
        int V = Integer.parseInt(br.readLine());  
        vis= new int[N+1];  
  
        StringTokenizer st;  
        //인접 리스트 활용 예정  
  
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();  
  
        for(int i=0;i  < N+1; i++){//0부터 N번까지  
            ArrayList<Integer> arr = new ArrayList<>();  
            list.add(arr);  
        }  
  
  
        for(int i=0; i<V; i++){  
            st = new StringTokenizer(br.readLine());  
  
            int x = Integer.parseInt(st.nextToken());  
            int y = Integer.parseInt(st.nextToken());  
  
            list.get(x).add(y);  
            list.get(y).add(x);  
        }  
  
        find(1, list);  
  
        int answer=0;  
        for(int x : vis){  
            if(x==1){  
                answer++;  
            }  
        }  
        System.out.println(--answer);  
    }  
  
    private static void find(int start, ArrayList<ArrayList<Integer>> list){  
        Queue<Integer> q = new LinkedList<>();  
  
        q.add(start);  
        vis[start] =1;  
  
        while(!q.isEmpty()){  
            int cur = q.poll();  
            for(int x : list.get(cur)){  
                if(vis[x]==0){  
                    q.add(x);  
                    vis[x]=1;  
                }  
            }  
        }  
    }  
  
}

노드에 연결된 값을 Queue를 통한 BFS를 통해 탐색했다.
이때 인접 리스트를 활용해서 순회를 돌도록 설정했다.

인접행렬과 재귀를 활용한 dfs문제 풀이

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.sql.SQLOutput;  
import java.util.*;  
  
class Main {  
    static int [] vis;  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
  
        int N = Integer.parseInt(br.readLine());  
  
        int V = Integer.parseInt(br.readLine());  
        vis= new int[N+1];  
  
  
        //인접 행렬  
        int[][] arr = new int[N+1][N+1];  
  
        StringTokenizer st;  
        //인접 리스트 활용 예정  
  
        for(int i=0; i<V; i++){  
            st = new StringTokenizer(br.readLine());  
  
            int x = Integer.parseInt(st.nextToken());  
            int y = Integer.parseInt(st.nextToken());  
  
            //무방향 인접 행렬 생성  
            arr[x][y]=1;  
            arr[y][x]=1;  
        }  
  
        find(1, arr);  
  
        int answer=0;  
  
        for(int x : vis){  
            if(x==1){  
                answer++;  
            }  
        }  
        System.out.println(--answer);  
    }  
  
    private static void find(int start, int[][] arr){  
      vis[start]=1;  
  
      for(int i=0; i<arr.length;i++){  
          if(arr[start][i]==1 && vis[i]==0){//start번의 행과 연결된 노드가 있고 해당 노드가 검사를 안한 친구라면?  
              find(i,arr);  
          }  
      }  
    }  
  
}

private static void find(int start, ArrayList<ArrayList<Integer>> list){  
        Queue<Integer> q = new LinkedList<>();  
  
        q.add(start);  
        vis[start] =1;  
  
        while(!q.isEmpty()){  
            int cur = q.poll();  
            for(int x : list.get(cur)){  
                if(vis[x]==0){  
                    q.add(x);  
                    vis[x]=1;  
                }  
            }  
        }  

Queue에 인접한 노드들을 넣어주는 방식이다. Queue에 노드를 넣는 순간 vis에 해당 노드는 검사를 수행한 노드라고 표시한다. 예를 들어서

1 번과 연결된 노드가 2, 3이라고 가정하자
1. Queue에는 1 번과 연결된 2번 3 번의 노드가 저장된다. [2,3]
2. 2번 3번이 연결되어 있는 것을 확인했으니 vis에 표시를 해준다. vis[2]=1 , vis[3]=1
3. 그 다음 Queue에서 poll을 수행한다.2번이 나오게 된다.Queue에 남은 숫자3
4. 2번 노드와 연결된 노드 지점들을 찾는다. 위 그림에서는 4번과 1번이 된다.
5. 이때 1번은 시작점으로 표시가 되었으니 skip 4번의 노드를 queue에 넣는다. 3,4
6. 3번을 꺼내서 3번 노드와 연결된 친구들을 넣는다. 이때 2를 넣는데 2번에서 node2번은 이미 지나간 경로이다. 따라서 해당 노드를 Queue에 넣지 않는다!
7. 마지막 queue에서 4번을 꺼낸다.
8. 4번의 연결리스트와 연결된 노드는 1이다. 하지만 1 또한 처음에 시작으로 지나간 노드이니 검사하지 않는다.

위의 결과로 1번과 연결된 노드는 2,4가 나오게된다.

참고로 인접 행렬도 동일하게 풀 수 있다.
행이 의미하는것은 노드 N 그리고 열의 값 K가 의미하는 것은 노드 N번과 연결된 다른 노드를 의미한다.
즉 내가 탐색하고 싶은 행의 select하고 그 행의 열을 돌면서 1로 표시된 부분의 노드를 Queue혹은 재귀를 통해 탐색하는 것이다.

REVIEW

그래프 문제는 전혀 감을 잡지 못했는데 이제 인접행렬, 인접 리스트를 공부하고 나서 좀 풀게된 느낌!