[백준 | Java] 1707번 이분 그래프

1707번 / 이분 그래프

❓ 이분 그래프

🏷️ 관련 주제 : DFS BFS 이분 그래프

💦 나의 시도

처음에 재귀함수를 사용한 DFS로 해결해 보려했지만 코드를 어떻게 짜야할 지 잘 그려지지 않음.

Try01. 재귀함수를 사용한 DFS로 해결해 보려했지만 코드를 어떻게 짜야할 지 잘 그려지지 않음.

💽 메모리 초과

Try02. 세 개의 점이 삼각형을 그리게 연결되어 있으면 No 출력!

이분 그래프를 어떻게 가려내야할 지 아직 감이 잡히지 않은 상태에서
다른 블로그에서 예시로 든 이분 그래프를 보며
세 점이 삼각형을 그리며 연결되어 있으면 이분 그래프가 아닌 것 같아서
세 점이 연결되어 있는지 체크하기로 함.

삼각형 체크 코드

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

      public class Main {
          public static void main(String[] args) throws IOException {
              BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
              int K = Integer.parseInt(br.readLine());  // 테스트 케이스

              for (int i = 0; i < K; i++) {
                  StringTokenizer st = new StringTokenizer(br.readLine());
                  int V = Integer.parseInt(st.nextToken());  // 정점의 수
                  int E = Integer.parseInt(st.nextToken());  // 간선의 수

                  Map<Integer, ArrayList<Integer>> link = new HashMap<>();

                  for (int j = 0; j < E; j++) {
                      st = new StringTokenizer(br.readLine());
                      int u = Integer.parseInt(st.nextToken());
                      int v = Integer.parseInt(st.nextToken());

                      ArrayList<Integer> linkU = link.getOrDefault(u, new ArrayList<Integer>());
                      linkU.add(v);
                      link.put(u, linkU);
                      ArrayList<Integer> linkV = link.getOrDefault(v, new ArrayList<Integer>());
                      linkV.add(u);
                      link.put(v, linkV);
                  }

                  boolean flag = true;

                  for (int u : link.keySet()) {
                      ArrayList<Integer> linkU = link.get(u);
                      if (linkU.size() == 1) {
                          continue;
                      }
                      for (int v : link.get(u)) {
                          ArrayList<Integer> linkV = link.get(v);
                          if (linkV.size() == 1) {
                              continue;
                          }
                          for (int v2 : linkV) {
                              if (v2 == u) {
                                  continue;
                              }

                              if (linkU.contains(Integer.valueOf(v2))) {
                                  System.out.println("NO");
                                  flag = false;
                                  break;
                              }
                          }

                          if (!flag) {
                              break;
                          }
                      }

                      if (!flag) {
                          break;
                      }
                  }

                  if (flag) {
                      System.out.println("YES");
                  }
              }
          }
      }

⏱️ 시간 초과

어떻게 시간을 줄일 수 있을까? 고민하다 선이 한 개 연결된 점은 삭제해도 무방할 것 같아서
반복문을 돌며 삼각형을 그리는지 체크 전, 연결된 점이 한개인 점 삭제

간선 1개인 점 삭제 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine()); // 테스트 케이스

		for (int i = 0; i < K; i++) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());  // 정점의 수
          	int E = Integer.parseInt(st.nextToken());  // 간선의 수

          	Map<Integer, ArrayList<Integer>> link = new HashMap<>();

            for (int j = 0; j < E; j++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());

                if (u != v) {
                    ArrayList<Integer> linkU = link.getOrDefault(u, new ArrayList<Integer>());
                    linkU.add(v);
                    link.put(u, linkU);
                    ArrayList<Integer> linkV = link.getOrDefault(v, new ArrayList<Integer>());
                    linkV.add(u);
                    link.put(v, linkV);
                }
            }

            Set<Integer> keys = new HashSet<>(link.keySet());
            for (int u : keys) {
                if (link.get(u).size() == 1) {
                    link.remove(u);
                }
            }

            boolean flag = true;

            for (int u : link.keySet()) {
                ArrayList<Integer> linkU = link.get(u);
                for (int v : linkU) {
                    if (link.containsKey(v)) {
                        for (int v2 : link.get(v)) {
                            if (v2 == u) {
                                continue;
                            }

                            if (linkU.contains(Integer.valueOf(v2))) {
                                System.out.println("NO");
                                flag = false;
                                break;
                            }
                        }
                    }
                    if (!flag) {
                        break;
                    }
                }

                if (!flag) {
                    break;
                }
            }

            if (flag) {
                System.out.println("YES");
            }
        }
	}
}

⏱️ 시간 초과

시간을 더 줄일 수 있는 방법이 없을까? 고민하다 갑자기 DFS 풀이가 머릿속에 번득임!

Try03. 재귀함수를 이용한 DFS

1. BufferedReader를 통해 테스트 케이스 int K를 입력 받아 int형으로 변환 후, K에 할당
2. 0 ~ (K - 1) 범위에서 반복문을 돌며 정점의 수 int V와 간선의 수 int E를 입력 받고 int형으로 변환 후, 해당 변수에 할당
3. 각 정점의 번호를 키로 해당 정점에 연결된 정점들의 번호를 담은 ArrayList를 값으로 하는 인스턴스 변수 Map link를 초기화
4. 각 정점을 방문했는지 체크하는 boolean[] visited를 길이 V로 초기화
5. 0 ~ (E - 1) 범위를 반복문을 돌며 간선에 연결된 두 정점 int u, v를 StringTokenizer를 통해 입력받고 nextToken()메서드로 점을 한개씩 꺼내 int형으로 변환후, 각 변수에 할당
6. link에 u와 v 키가 존재할 수도 있고 그렇지 않을 수도 있으므로 getOrDefault()메서드로 각 정점을 키로 하는 값 혹은 새로운 ArrayList를 생성하여 가져와서 u에 연결된 정점들의 ArrayList를 linkU, v에 연결된 정점 ArrayList를 linkV에 할당
7. linkU에 v 추가 및 link에 u의 값으로 linkU 추가, linkV에 u 추가 및 link에 v의 값으로 linkV 추가
8. 해당 정점의 색을 저장하기 위한 인스턴스 변수 Map colors를 초기화
   • 키 : 정점의 번호
   • 값 : 정점의 색(1, -1)

---

이분 그래프 탐색 메서드 checkBipartite(int u, int color)

u : 탐색할 정점 번호
color : 탐색할 정점에 부여할 색의 값(1 or -1)

1. 만약 u가 이미 탐색한 점인 경우,
   • u의 색을 colors에서 가져와 colorU에 할당
   • colorU의 값이 color와 다르면 false를 반환하며 함수 종료
   • 값이 동일하면 true를 반환하며 함수 종료
2. 만약 u가 아직 탐색하지 않은 점인 경우,
   • visited[u - 1]에 true를 할당
   • colors에 정점 u의 색깔(값)로 color를 할당
   • 탐색하는 정점 u에 연결된 정점들을 담은 ArrayList를 link에서 가져와 ArrayList next에 할당
   • 결과값으로 반환할 boolean result를 true로 초기화
   • 탐색하는 정점 u에 연결된 점이 존재하면,
     • forEach문으로 각 점을 한개씩 꺼내(v) 재귀함수로 해당 점을 탐색, 이 때, color는 u의 색과 달라야 하므로 color * -1을 매개변수로 줌.
     • 위 재귀함수의 결과값을 result에 할당
     • 만약 result가 false이면 false를 반환하며 함수 종료
   • 반복문이 끝나면 최종 결과값 result를 반환하며 함수 종료

---

9. 1 ~ V 범위를 반복문을 돌며 해당 인덱스를 정점 u로 하여 만약 해당 점을 탐색하지 않았으면 checkPartite()메서드 실행하여 result에 할당
10. result가 false이면 "NO"를 출력하며 반복문 종료
11. 반복문이 모두 종료되고 result가 true이면 "YES"를 출력

맞았습니다!!

• 메모리 : 317300 KB
• 시간 : 1236 ms
• 코드 길이 : 2428 B

📑제출 기록 및 오답 원인

오늘도 풀이를 작성하며 코드를 계속 보다보니 불필요한 코드들이 보여서 처음 제출 성공 이후에도 몇 번 더 제출하였습니다.

 

💯 해결 방법

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

public class Main {
    public static Map<Integer, ArrayList<Integer>> link;
    public static Map<Integer, Integer> colors;
    public static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine());  // 테스트 케이스

        for (int i = 0; i < K; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());  // 정점의 수
            int E = Integer.parseInt(st.nextToken());  // 간선의 수

            link = new HashMap<>();
            visited = new boolean[V];

            for (int j = 0; j < E; j++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());

                ArrayList<Integer> linkU = link.getOrDefault(u, new ArrayList<Integer>());
                linkU.add(v);
                link.put(u, linkU);
                ArrayList<Integer> linkV = link.getOrDefault(v, new ArrayList<Integer>());
                linkV.add(u);
                link.put(v, linkV);
            }

            colors = new HashMap<>();
            boolean result = true;
            for (int u = 1; u <= V; u++) {
                if (!visited[u - 1]) {
                    result = checkBipartite(u, 1);

                    if (!result) {
                        System.out.println("NO");
                        break;
                    }
                }
            }

            if (result) {
                System.out.println("YES");
            }
        }
    }

    public static boolean checkBipartite(int u, int color) {
        if (visited[u - 1]) {
            int colorU = colors.get(u);

            if (color != colorU) {
                return false;
            }

            return true;
        }

        visited[u - 1] = true;
        colors.put(u, color);

        ArrayList<Integer> next = link.get(u);
        boolean result = true;

        if (next!= null) {
            for (int v : next) {
                result = checkBipartite(v, color * -1);

                if (!result) {
                    return result;
                }
            }
        }

        return result;
    }
}

🏷️ 문제 풀면서 참고한 블로그

• Java에서 세트 복제
• [알고리즘] 이분 그래프(Bipartite Graph)란
• 이분 그래프 - 위키백과, 우리 모두의 백과사전
• 자료구조 - 이분 그래프(Bipartite Graph)
• [백준 1707] 이분 그래프 (자바)