섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (1) 이분 그래프, 유니온 파인드

섹션 3. 코딩테스트 [실전편] - 08. 그래프

⬛ 08. 그래프

• 그래프는 노드와 엣지로 구성된 집합.
• 노드는 데이터 표현 단위, 에지는 노드를 연결

⬛ 08-1. 그래프의 표현

• 그래프 구현 방식은 크게 3가지가 있다.

🟦 1. 에지 리스트

• 에지 중심으로 그래프 표현하는 방식이다.

🟧 1) 가중치 X 그래프 표현

• 배열의 행 2개로 출발노드, 도착노드 표현한다.

🟧 2) 가중치 O 그래프 표현

• 배열 행 3개로 출발노드 도착노드, 가중치 표현한다.

🟦 2. 인접 행렬

• 2차원 배열 이용하여 노드 중심으로 표현하는 방식이다.
• 다만, 에지 탐색 시, N번 접근해야 하므로 노드 개수에 비해서 에지가 적을 때는 공간 효율성 떨어진다.

🟧 1) 가중치 X 그래프 표현

• i행 j열에 i → j 표현

🟧 2) 가중치 O 그래프 표현

• i행 j열에 i→ j의 값에 가중치 표현

🟦 3. 인접 리스트

• ArrayList<> 이용하여 그래프를 표현한다.

🟧 1) 가중치 X 그래프 표현

🟧 2) 가중치 O 그래프 표현

• 1) ArrayList [N] 배열 표현
• 2) ArrayList<ArrayList<> > () 중첩 리스트 표현

---

🟦 백준 18352번. 특정 거리의 도시 찾기

문제

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

입력

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.

출력

X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.

이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

풀이

• 도시는 Node가 되고, 도로가 Edge가 된다.
• 특정 X로부터 출발하여 인접 거리가 K가 되는 도시 출력을 하라고 되어있다.
• BFS를 사용하면 인접 거리 우선으로 탐색을 하게 된다.
• 따라서 BFS를 사용하며 visited[int]형으로 직전 cur 정점의 거리 + 1 처리를 해가면서 출발점으로부터의 거리를 담아두면 된다. 담긴 건 거리값이고 출력은 인덱스를 해야 도시가 특정된다.
• ArrayList 형으로 answer에 거리K인 인덱스를 담았는데, 만약 size()==0인 경우 정답이 없다는 것이므로-1 출력을 하도록 하고, 그 외의 경우에는 각각 담긴 값을 출력시켰다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/* 백준 18352번. 특정 거리의 도시 찾기 */
public class Main {
    static int N, M, K, S;
    //방문여부
    static int visited[];//여기에 인접 거리 저장할 거라
    static ArrayList<ArrayList<Integer>> graph;

    //BFS
    static void BFS(int n) {
        Queue<Integer> Q = new LinkedList<>();
        visited[n] = 1;
        Q.add(n);

        while(!Q.isEmpty()) {
            int cur = Q.poll();
            for(int nx : graph.get(cur)) {
                if(visited[nx] == 0) { //방문 안한 인접 정점에 대하여 
                    Q.add(nx);
                    visited[nx] = visited[cur] + 1;//이전 정점 + 1 거리 처리 
                }
            }
        }
    }

    //실행 메인
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb= new Scanner(System.in);

        N = kb.nextInt();
        M = kb.nextInt();
        K = kb.nextInt();
        S = kb.nextInt();

        //공간 생성 
        visited = new int[N+1];
        graph = new ArrayList<>();

        for(int i=0; i<=N; i++) {
            graph.add(new ArrayList<Integer>());
        }

        //입력받기
        for(int i=0; i<M; i++){
            int a= kb.nextInt();
            int b= kb.nextInt();

            graph.get(a).add(b);
        }

        //호출
        BFS(S);//시작점은 S

        ArrayList<Integer> answer = new ArrayList<>();
        //정답 출력 K+1 과 값이 같은 애가 정답임
        for(int i=1; i<=N; i++) {
            if(K+1 == visited[i]) {
                answer.add(i); //그 인덱스 출력 
            }
        }
        //만약에 그 값이 없었다면 
        if(answer.size() == 0) {
            System.out.println(-1);
        }else {
            for(int x : answer) {
                System.out.println(x);
            }
        }
    }
}

---

🟦 백준 1325번. 효율적인 해킹

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

풀이

• 결국 가장 많이 해킹할 수 있는 컴퓨터 == 가장 많은 신뢰를 받는 컴퓨터
• ==즉. 가장 많이 방문을 당한 애를 출력하면 되는 것이다.
• 즉, 인접 정점으로 방문할 때마다, ++ 처리해서 가장 많이 방문된 정점의 max값 인덱스를 오름차순 출력하면 된다.

package to_0621_2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/*백준 1325번. 효율적인 해킹 */
public class Main {
    static int N, M;

    static boolean visited[];
    static int answer[];
    static ArrayList<ArrayList<Integer>> graph;
    //BFS
    static void BFS(int n) {
        Queue<Integer> Q = new LinkedList<>();
        Q.add(n);
        visited[n] = true;

        while(!Q.isEmpty()) {
            int cur = Q.poll();
            for(int nx : graph.get(cur)) {
                if(!visited[nx]) {
                    visited[nx] = true;
                    Q.add(nx);
                    answer[nx]++;//방문할 때마다 ++ 처리
                }
            }
        }
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb = new Scanner(System.in);

        N = kb.nextInt();
        M = kb.nextInt();

        answer = new int[N+1];
        graph = new ArrayList<>();
        for(int i=0; i<N+1; i++) {
            graph.add(new ArrayList<Integer>());
        }

        //입력받기
        for(int i=0; i<M; i++) {
            int a = kb.nextInt();
            int b= kb.nextInt();
            graph.get(a).add(b);
        }

        //각 모든 노드에 대하여 
        for(int i=1; i<=N; i++) {
            visited = new boolean[N+1];
            BFS(i);
        }

        //출력
        int max = Integer.MIN_VALUE;
        for(int x : answer) {
            if(x > max) {
                max = x;
            }
        }

        for(int i=0; i<N+1; i++) {
            if(answer[i] == max) {
                System.out.print(i+" ");
            }
        }
    }
}

---

⬛ 추가 | 이분 그래프 (bipartite graph)

• 각 집합에 속한 노드끼리 서로 인접하지 않는 두 집합으로 그래프 노드를 나눌 수 있을 때, 이 그래프를 이분 그래프라고 한다.
• 즉, 정점을 어떠한 방법으로든 두 개의 집합으로 나눴을 때 각 집합의 정점끼리 간선이 존재하지 않게 나눌 수만 있다면 이분 그래프이다.

• 이 그림에서 1, 2, 3번 그림은 이분 그래프가 가능하다.
• 4번 그래프는 이분 그래프가 아니다.
• 이와 같이 홀수 길이의 사이클이 있다면 이분 그래프가 될 수 없다.

🟦 이분 그래프 판별 방법

이분 그래프 판별방법은 다음과 같다.

1. 모든 정점에 대해 각 정점에서 dfs 혹은 bfs를 진행하면서 2개 종류의 집합을 번갈아가며 설정한다. (뭐 true, false로 하던지 -1,1로 하던지 상관없다. 체크만 가능하면 된다.)
2. 이 때 dfs 혹은 bfs를 진행하다가 인접한(간선이 연결된) 정점이 자신과 동일한 종류의 집합이라면 이분 그래프가 아니다. 모두 통과되었다면 이분 그래프이다.

• 즉, 탐색한 노드에 다시 접근하게 되었을 때, 현재 노드의 집합과 같다면 이분 그래프가 불가능하다는 사실로 판별

 

🟦 백준 1707번. 이분 그래프

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

풀이

• 일단 직전 방문 정점 v와 현재 방문 정점x 가 동일 집합인경우 사이클이 발생했으므로 이분 그래프는 불가능
• 애초에 처리 시 , 인접한 정점의 경우 다른 집합 소속이 되도록 나누었는데도, 방문한 직전 정점과 현 정점이 동일 집합이 되었다는 것이 사이클 발생을 의미함

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

/* 백준. 1707번. 이분 그래프 판별 문제 
 *  */
public class Main {
    static ArrayList<ArrayList<Integer>> graph;
    static int[] chk;
    static boolean[] visited;
    static boolean IsEven;//이분 탐색 여부
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    //static
    static void DFS(int v) {
        visited[v] = true;
        for(int x : graph.get(v)) {
            if(!visited[x]) {//방문 안한 인접 정점인 경우 다른 집합 소속 
                chk[x] = (chk[v] + 1) % 2; //2개로만 나누면 되니까 
                DFS(x);//더 깊이 탐색
            }
            else if(chk[v] == chk[x]) { //이미 방문한 직전 노드가 현재 노드와 동일 집함== 사이클 형성 시  
                IsEven= false; //이분 그래프 불가능 
            }
        }
    }


    //실행 메인 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        ArrayList<String > answer = new ArrayList<>();

        int T = Integer.parseInt(br.readLine());

        for(int t=0; t<T; t++) {
            String[] s = br.readLine().split(" ");//공백 기준 나누고
            int V = Integer.parseInt(s[0]);
            int E = Integer.parseInt(s[1]);

            graph = new ArrayList<>();
            visited = new boolean[V+1];
            chk = new int[V+1];
            IsEven = true;
            for(int i=0; i<=V; i++) {
                graph.add(new ArrayList<Integer>());
            }

            for(int i=0; i<E; i++) {
                s = br.readLine().split(" ");
                int St= Integer.parseInt(s[0]);
                int Ed =Integer.parseInt(s[1]);

                graph.get(St).add(Ed);
                graph.get(Ed).add(St);
            }

            for(int i=1; i<=V; i++) {
                if(IsEven) {
                    DFS(i);
                }else {
                    break;
                }
            }

            if(IsEven) {
                answer.add("YES");
            }else {
                answer.add("NO");
            }
        }

        //정답 출력 
        for(String a : answer) {
            System.out.println(a);
        }

    }
}

---

 

⬛ 08-2. 유니온 파인드

🟦 유니온 파인드 (Union & Find)

• 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결하여 1개의 집합으로 묶는 ‘Union 연산’ + 두 노드가 같은 집합에 속해있는지 확인하는 ‘Find 연산’으로 구성된 알고리즘

🟧 유니온 파인드 핵심 이론

• 1) Union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산
• • ex. Union(a, b) → a U b 가 되도록 함
• 2) Find 연산 : 특정 노드 a에 관해 a 소속 집단의 대표 노드 반환하는 연산
• • ex. Find(a) → a 집합 대표 노드 반환되도록 함

---

🟦 백준 1717번. 집합의 표현

코드

import java.util.ArrayList;
import java.util.Scanner;

/*1707 집합의 표현 */
public class Main {
    static int [] parent;//부모 저장용
    //find
    static int find(int a) {
        if(a == parent[a]) return a;
        else {
            return parent[a] = find(parent[a]);
        }
    }

    //union
    static void union(int a, int b) {
        a = find(a); //부모 찾고 
        b = find(b); //부모 찾고 
        if(a!=b) {
            parent[b] = a;//a를 부모로 갱신 처리 
        }
    }
    //chkSame
    static boolean chkSame(int a, int b) {
        a = find(a);
        b = find(b);
        if(a == b) return true;
        else return false;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb = new Scanner(System.in);

        ArrayList<String > answer = new ArrayList<>();

        int N = kb.nextInt();
        int M = kb.nextInt();

        parent = new int[N+1];

        //초기화
        for(int i=0; i<N+1; i++) {
            parent[i] = i;//자기 자신으로 초괴화
        }

        for(int i=0; i<M; i++) {
            int Q=kb.nextInt();
            int a=kb.nextInt();
            int b=kb.nextInt();

            if(Q==0) {
                union(a, b);
            }else {
                if(chkSame(a,b)) {
                    answer.add("YES");
                }else {
                    answer.add("NO");
                }
            }
        }

        for(String x : answer) System.out.println(x);
    }
}

---

🟦 백준 1976번. 여행 계획 짜기

문제

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

입력

첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000이하이다. 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다. 마지막 줄에는 여행 계획이 주어진다. 도시의 번호는 1부터 N까지 차례대로 매겨져 있다.

출력

첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.

풀이

• 인접행렬로 입력받은 연결 정보의 도시들이 실제로 union 처리 후, route상에 담긴 여행 계획 순으로 탐색하면서 그 find(route[i]) 후에도 모든 부모의 값이 같은 경우 하나의 연결 경로로 연결된 상태이니 YES 가 된다.

import java.util.Scanner;

/*1976번. 여행 가자 
 *  도시의 연결 유무를 유니온 파인드 연산으로 해결할 수 있다는 아이디어
 * */
public class Main {
    static int[][] city;//도시 연결 정보 
    static int [] parent;//연결 부모 
    static int[] route;//도시 루트 
    //find
    static int find(int a) {
        if(a == parent[a]) return a;
        else {
            return parent[a] =find(parent[a]);
        }
    }

    //union
    static void union(int a, int b) {
        a= find(a);
        b=find(b);
        if(a!=b) {
            a = Math.max(a, b);
            b = Math.min(b, a);
            parent[b] = a;
        }
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb= new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();

        city = new int[n+1][n+1];

        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                city[i][j] = kb.nextInt();
            }
        }

        //루트 연결 정보 
        int[] route = new int[m+1];
        for(int i=1; i<=m; i++) {
            route[i] = kb.nextInt();
        }
        //부모값 초기화 
        parent = new int[n+1];
        for(int i=1; i<=n; i++) {
            parent[i]= i;
        }

        for(int i=1; i<=n; i++) {
            for(int j =1; j<=n; j++) {
                if(city[i][j]==1) {//두 도시가 연결되어 있다면
                    union(i, j);
                }
            }
        }

        //연결 여부 ㅇㅇx
        int index = find(route[1]);
        for(int i = 2; i<route.length; i++) {
            if(index != find(route[i])) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }
}