이분 그래프 [백준 1707][골드4][Java]

 

[광고 누르면 오늘의 행운 상승!!]

 

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

 

1707번: 이분 그래프

그래프 문제

이분그래프란?
인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프.

그래프의 모든 정점이 두 집합으로 나눠지고 서로 다른 그룹의 정점이
간선으로 연결되어져 있는 그래프를 이분 그래프라고 한다.

 

1. 두개의 팀을 만든다 RED= 1, GREEN = -1
2. 그래프의 인접요소를 방문하면서 색칠이 되어있지 않다면 자신과 다른 색깔로 색칠한다.
3. 이미 색칠이 되어있는 노드라면 자신과 비교한다
4. 같으면 빠져나오고 NO를 출력한다
5. 끝까지 NO가 출력되지 않으면 YES를 출력한다

<많이 틀린 이유>
1. 처음에 그래프를 visit[][]을 사용하여 방문 체크를 했다 -메모리 초과
2. visit[][]을 지우고 돌렸다 -메모리초과
3. graph를 int 에서 boolean 형으로 바꿨다 - 메모리초과
4. 너무 화가 나서 리스트 형태로 바꿨다 (최대 20만개 메모리 절약)- 틀렸습니다.
5. 아 이제는 틀렸네 왜 틀렸지 아하 ans 값을 테스트 케이스마다 갱신을 안했구나 -틀렸습니다.
6. 아 뭐가 문제지 설마 노드가 1개일때 문제인가 아닌데 아 여기 오타가있네 - 틀렸습니다
7. 아 그래프가 한개가 아니구나.. 이어져있지 않은 정점이 있을 수가 있구나 -맞았습니다.

package Study0307;

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

public class 이분그래프 {

	public static int[] team;
	public static ArrayList<ArrayList<Integer>> graph;
	public static int V,E;
	public static String ans = "YES";
	public static int A,B;
	public static int RED = 1, GREEN = -1;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		
		for (int tc = 0; tc < T; tc++) {
			ans = "YES";
			V = sc.nextInt();
			E = sc.nextInt();
			
			graph = new ArrayList<>();
			
			for (int i = 0; i < V; i++) {
				graph.add(new ArrayList<>());
			}
			for (int i = 0; i < E; i++) {
				A = sc.nextInt()-1;
				B = sc.nextInt()-1;
				
				graph.get(A).add(B);
				graph.get(B).add(A);
			}
			team = new int[V];
			for (int i = 0; i < V; i++) {
				if(team[i] == 0) {
					if(!bfs(i)) break;
				}
			}
			
			System.out.println(ans);
		}
	}

	private static boolean bfs(int n) {
		Queue<Integer> q = new LinkedList<>();
		
		q.add(n);
		team[n] = RED;
		while(!q.isEmpty()) {
			int node = q.poll();
			
			for(Integer i : graph.get(node)) {
				if(team[node] == team[i]) {
					//인접한 곳이 나와 같은 팀인지 체크
					ans = "NO";
					return false;
				}
				if(team[i] == 0) {
					//방문하지 않았으면 자신과 반대되는 팀을 넣는다.
					team[i] = team[node]*-1;
					q.add(i);
				}
			}
		}
		
		return true;
	}
}