[알고리즘] 이분 그래프(백준 1707, 1953, 12893 -Java)

[알고리즘] 이분 그래프(백준 1707, 1953, 12893 -Java)

알고리즘 공부를 계속 미루는 제 자신을 보고 이대로는 안되겠다 싶어 😇
본격적으로 코딩테스트를 준비(+알고리즘 공부) 해보려고 합니다.
물론 혼자하면 작심삼일이 될거 같아
무료 Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의
강의 커리큘럼에 맞춰 공부해보자!!

[무료] Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의

이분 그래프

 

먼저 이분 그래프가 무엇인지 알아보자!
이분 그래프는 그래프 형태의 자료구조 입니다.
노드를 두 그룹으로 나누었을 때 같은 그룹의 노드 끼리는 간선으로 연결되어 있지 않은 경우의 그래프를 의미합니다.

 

백준 1707

1707번: 이분 그래프

이분 그래프 판별 방법

이분 그래프를 판별하는 방법은 DFS를 사용하면 됩니다.
이분 그래프는 두 그룹으로 분리해야 하기 때문에, 그룹 배열을 생성하여 DFS를 실행하면서 노드를 두 그룹으로 분리합니다.

만약 해당 노드에 방문했고, 탐색을 시도한 노드(출발 노드)와 그 노드와 연결된 노드(도착 노드)와 같은 그룹인지 판단합니다.
같은 그룹이면 이분 그래프가 아닙니다!!

이를 그림으로 설명하면 다음과 같습니다.

 

풀이

public class Quiz1707 {
    static boolean flag = true;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        // 테스트 갯수
        int k = Integer.parseInt(br.readLine());

        for(int t = 0 ; t < k; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            // 노드 갯수
            int v = Integer.parseInt(st.nextToken());
            // 간선 갯수
            int e = Integer.parseInt(st.nextToken());

            // 인접 리스트 생성(index 0은 사용하지 않음)
            List<Integer>[] lists = new ArrayList[v+1];
            // 인접 리스트 초기화
            for(int i = 1; i <= v; i++) {
                lists[i] = new ArrayList<>();
            }

            // 인접 리스트 저장
            for(int i = 0; i < e; i++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());

                // 양방향
                lists[start].add(end);
                lists[end].add(start);
            }

            // 노드 탐색 이력 배열
            boolean[] visited = new boolean[v+1];
            // 그룹 배열(0 또는 1로 표현)
            int[] group = new int[v+1];
            // 노드 갯수만큼 이분 그래프 탐색
            for(int i = 1; i <= v; i++) {
                dfs(lists, visited, group, i);
            }
            if(flag) {
                sb.append("YES").append("\n");
            }
            else {
                sb.append("NO").append("\n");
            }
            // 초기화
            flag = true;
        }
        System.out.print(sb);
        br.close();
    }

    private static void dfs(List<Integer>[] lists, boolean[] visited, int[] group, int start) {
        visited[start] = true;
        // 해당 노드의 인접노드의 갯수만큼 탐색(시작노드의 도착노드 갯수만큼 탐색)
        for(int j = 0; j < lists[start].size(); j++) {
            // 인접 노드
            Integer adjacentNode = lists[start].get(j);
            // 인접 노드에 탐색 이력이 없으면
            if(!visited[adjacentNode]) {
                // 인접노드의 그룹을 시작노드의 그룹과 다른 집합으로 분류
                group[adjacentNode] = (group[start] + 1) % 2; // 0이면 1로, 1이면 0으로
                // 인접노드 dfs 탐색
                dfs(lists, visited, group, adjacentNode);
            }
            // 시작 노드와 인접 노드가 같은 그룹이면
            else if(group[start] == group[adjacentNode]) {
                // 이분 그래프가 아님!
                flag = false;
            }
        }
    }
}

백준 1953

1953번: 팀배분

문제가 처음에는 이해가 잘 되지 않았는데
입력 예시를 보고 이해했습니다.

입력 예시

5        // 학생수
1 3      // 1번이 싫어하는 사람 수 1명, 3번이랑 팀 X
1 5      // 2번이 싫어하는 사람 수 1명, 5번이랑 팀 X
2 1 4    // 3번이 싫어하는 사람 수 2명, 1, 4번이랑 팀 X
1 3      // 4번이 싫어하는 사람 수 1명, 3번이랑 팀 X
1 2      // 5번이 싫어하는 사람 수 1명, 2번이랑 팀 X

인접 리스트에 해당 입력을 넣고,
문제 요구사항이 같은 팀으로 배정하면 안되기 때문에 같은 팀이면 다른 팀으로 분리해준다.

 

풀이

public class Quiz1953 {
    /**
     * 5        // 학생수
     * 1 3      // 1번이 싫어하는 사람 수 1명, 3번이랑 팀 X
     * 1 5      // 2번이 싫어하는 사람 수 1명, 5번이랑 팀 X
     * 2 1 4    // 3번이 싫어하는 사람 수 2명, 1, 4번이랑 팀 X
     * 1 3      // 4번이 싫어하는 사람 수 1명, 3번이랑 팀 X
     * 1 2      // 5번이 싫어하는 사람 수 1명, 2번이랑 팀 X
     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 학생 수
        int n = Integer.parseInt(br.readLine());

        // 인접 리스트 초기화
        List<Integer>[] list = new ArrayList[n+1];
        for(int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        // 인접 리스트 저장
        for(int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            // 싫어하는 사람 수
            int num = Integer.parseInt(st.nextToken());
            for(int j = 0; j < num; j++) {
                // 싫어하는 사람
                int hateMan = Integer.parseInt(st.nextToken());

                // 서로 싫어함
                list[i].add(hateMan);
                list[hateMan].add(i);
            }
        }

        // 탐색 이력
        boolean[] visited = new boolean[n+1];
        // 팀
        int[] group = new int[n+1];
        // 학생 수 만큼 탐색
        for(int i = 1; i <= n; i++) {
            dfs(list, visited, group, i);
        }

        // 청팀, 백팀
        // group의 index가 사람, group[index]가 팀
        int count0 = 0;
        int count1 = 0;
        List<Integer> count0List = new ArrayList<>();
        List<Integer> count1List = new ArrayList<>();
        for(int i = 1; i <= group.length - 1; i++) {
            if(group[i] == 0) {
                count0++;
                count0List.add(i);
            } else {
                count1++;
                count1List.add(i);
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(count0).append("\n");
        for(Integer i : count0List) {
            sb.append(i).append(" ");
        }

        sb.append("\n").append(count1).append("\n");
        for(Integer i : count1List) {
            sb.append(i).append(" ");
        }

        System.out.print(sb);
        br.close();
    }

    private static void dfs(List<Integer>[] list, boolean[] visited, int[] group, int start) {
        visited[start] = true;
        for(int i = 0; i < list[start].size(); i++) {
            // 인접 노드
            Integer adjacentNode = list[start].get(i);
            // 인접 노드에 방문 이력이 없으면
            if(!visited[adjacentNode]) {
                // 서로 같은 팀이면 청팀, 백팀 구분한다.
                if(group[adjacentNode] == group[start]) {
                    group[adjacentNode] = (group[start] + 1) % 2;
                }
                dfs(list, visited, group, adjacentNode);
            }
        }
    }
}

백준 12893

12893번: 적의 적
적대관계, 우호관계 2가지 그룹으로 존재할 수 있는지 확인하면 되는 문제입니다.
즉, 이분 그래프가 가능한지 확인하면 됩니다.
DFS를 이용하여 탐색하고 이분 그래프가 가능한지 확인했습니다.

 

풀이

public class Quiz12893 {
    static boolean theory = true;
    public static void main(String[] args) throws IOException {
        /**
         * 적의 적은 친구
         * 적대관계, 우호관계 2가지 그룹으로 존재할 수 있는지
         * 즉, 이분 그래프가 가능한지?
         */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 노드 수
        int n = Integer.parseInt(st.nextToken());
        // 간선 수
        int e = Integer.parseInt(st.nextToken());

        // 인접 리스트 초기화
        List<Integer>[] list = new ArrayList[n+1];
        for(int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        // 적대 관계 저장
        for(int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            // 서로 적대 관계
            list[start].add(end);
            list[end].add(start);
        }

        // 탐색 이력
        boolean[] visited = new boolean[n+1];
        // 관계(적대 관계: 0, 우호관계: 1)
        int[] group = new int[n+1];
        // 노드 수 만큼 탐색
        for(int i = 1; i <= n; i++) {
            dfs(list, visited, group, i);
        }

        if(theory) {
            System.out.print(1);
        } else {
            System.out.print(0);
        }
        br.close();
    }

    private static void dfs(List<Integer>[] list, boolean[] visited, int[] group, int start) {
        visited[start] = true;
        for(int i = 0; i < list[start].size(); i++) {
            // 인접 노드
            Integer adjacentNode = list[start].get(i);
            // 탐색 이력이 없으면
            if(!visited[adjacentNode]) {
                // 관계 변경(우호 관계는 적대로, 적대관계는 우호로 변경)
                group[adjacentNode] = (group[start] + 1) % 2;
                dfs(list, visited, group, adjacentNode);
            }
            // 관계가 동일하면
            else if (group[adjacentNode] == group[start]) {
                // 이론 성립 안함
                theory = false;
            }
        }
    }
}