[Algorithm] 99클럽 코테 스터디 9일차 TIL | 백준_이분 그래프(1707번)

2025. 1. 23. 19:49·Algorithm

https://www.acmicpc.net/problem/1707


이분 그래프는 정점을 두 그룹으로 나눌 수 있어야 하는데,

 

ArrayList<Integer> [] 배열을 사용하여 인접 리스트를 생성하고

ArrayList<Integer>[] graph = new ArrayList[V];
for(int j = 0; j < V; j++){
    graph[j] = new ArrayList<>();
}
for(int j = 0; j < E; j++){
    st = new StringTokenizer(br.readLine());
    int node1 = Integer.parseInt(st.nextToken()) - 1;
    int node2 = Integer.parseInt(st.nextToken()) - 1;

    graph[node1].add(node2);
    graph[node2].add(node1);
}

 

colors가 0이면 미방문 정점

처음 방문하게 되는 정점을 1로 두고

그 정점과 인접한 정점들은 -1로 설정한다.

 

만약 인접한 정점과 현재 정점이 같다면? 이분 그래프가 아니다!

public static boolean bfs(int n, ArrayList<Integer>[] graph, int[] colors){
    Queue<Integer> queue = new LinkedList<>();
    queue.add(n);
    colors[n] = 1;

    while(!queue.isEmpty()){
        int current = queue.poll();
        for(int g : graph[current]){
            if(colors[g] == colors[current]){
                return false;
            }
            if(colors[g] == 0){
                colors[g] = -colors[current];
                queue.add(g);
            }
        }
    }
    return true;
}

 

인접 정점이 다음과 같을 때를 대비하여

1--2

3--4

5--4

3--5

for(int j = 0; j < V; j++){
    if(colors[j] == 0){
        if(!bfs(j, graph, colors)){
            result = false;
            break;
        }
    }
}

위 코드가 추가되어야 한다.

 

위 코드가 없으면

1--2만 돌고 검사를 끝내기 때문이다..

 

 

전체 코드

import java.util.*;
import java.io.*;
class Main{
    static StringBuilder answer = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i = 0; i < K; i++){
            st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            //ArrayList를 요소로 갖는 배열
            ArrayList<Integer>[] graph = new ArrayList[V];
            for(int j = 0; j < V; j++){
                graph[j] = new ArrayList<>();
            }
            for(int j = 0; j < E; j++){
                st = new StringTokenizer(br.readLine());
                int node1 = Integer.parseInt(st.nextToken()) - 1;
                int node2 = Integer.parseInt(st.nextToken()) - 1;

                graph[node1].add(node2);
                graph[node2].add(node1);
            }
            int[] colors = new int[V];
            boolean result = true;
            for(int j = 0; j < V; j++){
                if(colors[j] == 0){
                    if(!bfs(j, graph, colors)){
                        result = false;
                        break;
                    }
                }
            }
            answer.append(result ? "YES" : "NO").append("\n");
        }
        System.out.println(answer);
    }
    public static boolean bfs(int n, ArrayList<Integer>[] graph, int[] colors){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);
        colors[n] = 1;

        while(!queue.isEmpty()){
            int current = queue.poll();
            for(int g : graph[current]){
                if(colors[g] == colors[current]){
                    return false;
                }
                if(colors[g] == 0){
                    colors[g] = -colors[current];
                    queue.add(g);
                }
            }
        }
        return true;
    }
}

 

 

'Algorithm' 카테고리의 다른 글

[Algorithm] 99클럽 코테 스터디 11일차 TIL | 백준_체스판 다시 칠하기(1018번)  (0) 2025.02.03
[Algorithm] 99클럽 코테 스터디 10일차 TIL | 백준_빙산(2573번)  (4) 2025.01.24
[Algorithm] 99클럽 코테 스터디 8일차 TIL | 백준_단지번호붙이기(2667번)  (1) 2025.01.22
[Algorithm] 99클럽 코테 스터디 7일차 TIL | 백준_숨바꼭질(1697번)  (1) 2025.01.21
[Algorithm] 99클럽 코테 스터디 6일차 TIL | 백준_DFS와 BFS(1260번)  (4) 2025.01.20
'Algorithm' 카테고리의 다른 글
  • [Algorithm] 99클럽 코테 스터디 11일차 TIL | 백준_체스판 다시 칠하기(1018번)
  • [Algorithm] 99클럽 코테 스터디 10일차 TIL | 백준_빙산(2573번)
  • [Algorithm] 99클럽 코테 스터디 8일차 TIL | 백준_단지번호붙이기(2667번)
  • [Algorithm] 99클럽 코테 스터디 7일차 TIL | 백준_숨바꼭질(1697번)
dev_ajrqkq
dev_ajrqkq
알고리즘 천재가 될 거야
  • dev_ajrqkq
    기록이 자산이다
    dev_ajrqkq
  • 전체
    오늘
    어제
    • 분류 전체보기 (147)
      • Front-end (0)
      • Back-end (11)
        • Spring (1)
        • Java (8)
      • CS (9)
        • 데이터베이스 (5)
        • 네트워크 (4)
      • Algorithm (80)
      • 이것저것 (0)
      • 버그잡기 (1)
      • TIL (37)
      • 후기 (1)
      • 취준 (0)
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

      티스토리챌린지
      코딩테스트준비
      TypeScript
      항해99
      Til
      오블완
      99클럽
      개발자취업
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.2
    dev_ajrqkq
    [Algorithm] 99클럽 코테 스터디 9일차 TIL | 백준_이분 그래프(1707번)
    상단으로

    티스토리툴바