[백준] [BFS] [Union-Find] 2606.바이러스

2606. 바이러스

채점 현황

• 내 풀이- 오답
  • 입력 순서가 달라지면 앞에서 먼저 루트노드 수정해준 값은 뒤에 업데이트가 안될 수 있음
  • 최상위루트를 찾을때 루트배열값에도 find() 적용해야 최상위루트를 찾을 수 있음.
  • union(x,y) 시에 x>y, y<x 다 고려해줘야한다.

package day15_dfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class JUN2606_ParkSomin {
    static int N, M, cnt;
    static int[] root;
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        M=Integer.parseInt(br.readLine());
        root=new int[N+1];
        //root값 초기화
        for (int i = 0; i < N+1; i++) {
            root[i]=i;
        }
        cnt=0;
        for (int i = 0; i < M; i++) {
            StringTokenizer st= new StringTokenizer(br.readLine());
            int x=Integer.parseInt(st.nextToken());
            int y=Integer.parseInt(st.nextToken());
            union(x,y);
        }

        for (int r: root) {
            if (r==1) cnt++;
        }
        System.out.println(Arrays.toString(root));
        if (cnt==0) System.out.println(cnt);
        else System.out.println(cnt-1); //1 자기자신 제외
    }

    private static void union(int x, int y){
        x=find(x);
        y=find(y);
        if (y>x){
            root[y]=x;
        }
        if(y<x){
            root[x]=y;
        }
    }
    private static int find(int x){
        if (root[x]==x){
            return x;
        }
        root[x]=find(root[x]);
        return root[x];
    }

}

 

• 오답 수정

package day15_dfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class JUN2606_ParkSomin {
    static int N, M, cnt;
    static int[] root;
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        M=Integer.parseInt(br.readLine());
        root=new int[N+1];
        //root값 초기화
        for (int i = 0; i < N+1; i++) {
            root[i]=i;
        }
        cnt=0;
        for (int i = 0; i < M; i++) {
            StringTokenizer st= new StringTokenizer(br.readLine());
            int x=Integer.parseInt(st.nextToken());
            int y=Integer.parseInt(st.nextToken());
            union(x,y);
        }

        for (int r: root) {
            //if(r==1) 로 찾으면 안됨
            //입력순서에 따라 최상위루트가 아닌 그냥 하나 위 루트를 가리키고 있을 수 있기때문
            if (find(r)==1) cnt++;
        }

        if (cnt==0) System.out.println(cnt);
        else System.out.println(cnt-1); //1 자기자신 제외
    }

    private static void union(int x, int y){
        x=find(x);
        y=find(y);
        if (y>x){
            root[y]=x;
        }
        if(y<x){
            root[x]=y;
        }
    }
    private static int find(int x){
        if (root[x]==x){
            return x;
        }
        root[x]=find(root[x]);
        return root[x];
    }

}

 

---

• BFS