[BFS][Java][BOJ] #1707. 이분 그래프

#BFS  #Gold4

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

 

🌷 문제 설명

✏️ 백준 연습문제: #1707. 이분 그래프
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

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

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

입출력 예

입력	출력
2 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2	YES NO

 

 

💡 해결 포인트

1.  BFS인 것 눈치채기
- 🤖 DFS도 가능하지만 재귀 깊이 문제 생길 가능성 있음. DFS로도 같은 문제를 해결할 수 있음. 하지만 입력 크기가 커질 경우, 재귀 호출로 인해 스택 오버플로우 위험이 있음. 반면 BFS는 큐를 사용하므로 이러한 문제가 발생하지 않아 안정적.

2. 자바 식별자는 대소문자를 구별한다
- 근데 저렇게 변수명 쓰는게 권장되는지는 모르겠음. (V, v 두개 같이 씀)

 

 

🌷 내 코드

1.  BFS

import java.util.*;
import java.io.*;

public class BOJ_1707 {
    public static void main(String[] args) throws IOException {
      System.setIn(new FileInputStream("example.txt"));
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      // 첫 번째 줄 입력
      int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수

      for (int i = 0; i < T; i++) { // TestCase 만큼 돌면서
        String[] firstLine = br.readLine().split(" ");
        int V = Integer.parseInt(firstLine[0]); // 정점의 개수
        int E = Integer.parseInt(firstLine[1]); // 간선의 개수
        
        ArrayList<Integer>[] graph = new ArrayList[V + 1]; // 인접리스트 생성
        int[] visited = new int[V + 1]; // 방문 여부 체크
        boolean isBipartite = true; // 이분 그래프 여부

        // 인접리스트 초기화
        for (int j = 1; j <= V; j++) {
          graph[j] = new ArrayList<>();
        }

        // 간선 정보 입력
        for (int j = 0; j < E; j++) {
          String[] edge = br.readLine().split(" ");
          int u = Integer.parseInt(edge[0]);
          int v = Integer.parseInt(edge[1]);
          graph[u].add(v);
          graph[v].add(u);
        }

        // BFS
        Queue<Integer> queue = new LinkedList<>();  
        for (int j = 1; j <= V; j++) { // 모든 정점에 대해
          if (visited[j] == 0) { // 방문하지 않은 정점이라면
            queue.add(j); // 큐에 넣고
            visited[j] = 1; // 방문 표시
          }

          while (!queue.isEmpty()) { // 큐가 빌 때까지
            int currV = queue.poll(); // 큐에서 정점을 꺼내서
            for (int next : graph[currV]) { // 인접한 정점에 대해
              if (visited[next] == 0) { // 방문하지 않은 정점이라면
                queue.add(next); // 큐에 넣고
                visited[next] = visited[currV] * -1; // 방문 표시
              } else if (visited[next] == visited[currV]) { // 방문한 정점인데 색이 같다면
                isBipartite = false; // 이분 그래프가 아님
                break;
              }
            }
          }
        }

        System.out.println(isBipartite ? "YES" : "NO"); // 결과 출력

        
      }
    }
}

 

 

🌷 코멘트

난 지피티가 터지면 알고리즘을 풀지 못해. 근데 역으로 말하면 지피티가 다 풀어주는 세상아닌가? 코테 왜 치는거? (????)
이런 의문과 불만이 있지만 결국 순응중 치매 예방이라고 생각하자

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!
~대가리 꽃밭인 디지털 노마드가 꿈이예요~
🧚‍♀️ Gyumin Lee
📧 gyumin.q.lee@gmail.com

qminlee723 - Overview