[백준] 1707 : 이분 그래프 - JAVA

• 이분그래프
  모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프
  

문제분석

트리의 경우 항상 이분 그래프가 된다는것을 알 수 있다.
사이클이 발생하지 않으면 탐색을 하면서 다음 노드를 이번 노드와 다른 집합으로 지정하면 되기 때문이다.
단, 사이클이 발생했을 때는 이분 그래프가 불가능 할 때가 있다.
1 -> 2 -> 3 -> 1 -> ... 이렇게 순환되는 3개의 노드로 이루어진 그래프가 그 경우이다.

어떻게 이떄를 도출할까?
바로 기존의 탐색 메커니즘에서 탐색한 노드에 다시 접근하게 됐을 때 현재 노드의 집합과 같으면 이분 그래프가 불가능하다는것으로 판별할 수 있다.

로직

1. 입력된 그래프 데이터를 인접 리스트로 구현한다.
2. 모든 노드로 각각 DFS를 수행한다. 현재 노드에서 연결된 노드 중 이미 방문한 노드가 나와 같은 집합이면 이분 그래프가 아닌것으로 판별한다. 이분그래프가 아니면 이후 노드는 탐색하지 않는다.
   -> 모든 노드로 DFS 수행하는 이유? 그래프의 모든 노드가 이어져있지 않고 여러 개의 부분 그래프로 이뤄진 케이스가 존재할 수 있기때문이다.
3. 이분 그래프 여부를 출력한다.
4. 사례 개수만큼 과정 1~3을 반복한다.

슈도코드

N(노드개수) M(에지 개수) check(이분그래프 체크 배열)
A(그래프 데이터 저장 인접 리스트) visited(방문 기록 저장 배열)
K(테스트 케이스)
for(N만큼 반복) {
	V(노드 개수)
    E(에지 개수)
    for(V만큼 반복) {
    	A각 초기화
    }
}
for(M만큼 반복) {
	A에 데이터 저장
}
for(V만큼 반복) {
	각 노드에서 DFS 실행 -> 결과가 이분 그래프 아니면 반복 종료 
}
정답 출력 

DFS {
	현재 노드 출력 
    visited배열에 방문 체크
    if(현재 노드와 연결 노드 중 방문하지 않은 노드로) {
    	현재 노드와 다른 집합으로 연결 노드 집합 저장 
        DFS실행
    }
    else {
    	이미 방문한 노드인데 나와 집합 같으면 이분 그래프 아님 
    }
}

Troubleshooting

public class Main {
static List<Integer>[] A;
static boolean[] visited;
static int[] check;
static boolean isEven;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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());
			A = new ArrayList[V+1];
			visited = new boolean[V+1];
			check = new int[V+1];
			isEven = true;
			for(int k=1; k<=V; k++) {
				A[k] = new ArrayList<>();
			}
			for(int j=0; j<E; j++) {
				st = new StringTokenizer(br.readLine());
				int u = Integer.parseInt(st.nextToken());
				int v = Integer.parseInt(st.nextToken());
				A[u].add(v);
				A[v].add(u);
			}
			for(int i=1; i<=V; i++) {
				if(isEven&&!visited[i]) DFS(i); //원인
				else break;
			}
			if(isEven) System.out.println("YES");
			else System.out.println("NO");
		}
	}
	public static void DFS(int node) {
		visited[node] =  true;
		for(int adjacency : A[node]) {
			if(!visited[adjacency]) {
				check[adjacency] = (check[node]+1)%2;
				DFS(adjacency);
			}
			else {
				if(check[adjacency] == check[node]) isEven = false;
			}
		}
	}
}

문제

틀렸습니다를 받았다.

원인

main에서 DFS를 차례대로 호출하는데, 방문하지않았을경우에만 호출하면 왜 안되나?
if(isEven&&!visited[i]) DFS(i);에서 조건문의 &&!visited[i]이 문제이다.

저 조건문이 false이면 else의 break를 만나 for문을 나가버리는데, 연결요소가 1개가 아니라 여러개일경우가 문제가 된다.
예를들어, 첫번째 연결요소는 이분그래프가 가능하고, 두번째 연결요소는 이분그래프가 불가능해서 결과적으로 "NO"를 출력해야한다고 보자.
for문에서 처음에 DFS(1)을 돌고 나와서 isEven == true는 맞지만, 이미 돌았던 곳도 돌도록 i가 처리가 된 for문에의해 그 이후 DFS(2)를 하려고할때 if문의 조건문에서 '!visited[2]' == false가 될것이다.
따라서 두번째 연결요소까지는 가지도못하고 끝나버린다.

그러면 DFS는 DSF(1)만해서 한 번만 돌게되고, 결과적으로는 YES가 출력될것이다.

해결

&&!visited[i]를 지우자.
이미 돌았던곳에 또 가는것이 시간낭비이기는 하지만, 이게 로직상 맞다.

제출코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.List;
import java.util.ArrayList;

public class Main {
static List<Integer>[] A;
static boolean[] visited;
static int[] check;
static boolean isEven;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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());
			A = new ArrayList[V+1];
			visited = new boolean[V+1];
			check = new int[V+1];
			isEven = true;
			for(int k=1; k<=V; k++) {
				A[k] = new ArrayList<>();
			}
			for(int j=0; j<E; j++) {
				st = new StringTokenizer(br.readLine());
				int u = Integer.parseInt(st.nextToken());
				int v = Integer.parseInt(st.nextToken());
				A[u].add(v);
				A[v].add(u);
			}
			for(int i=1; i<=V; i++) {
				if(isEven) DFS(i);
				else break;
			}
			if(isEven) System.out.println("YES");
			else System.out.println("NO");
		}
	}
	public static void DFS(int node) {
		visited[node] =  true;
		for(int adjacency : A[node]) {
			if(!visited[adjacency]) {
				check[adjacency] = (check[node]+1)%2;
				DFS(adjacency);
			}
			else {
				if(check[adjacency] == check[node]) isEven = false;
			}
		}
	}
}

공부한 사항

• 트리(자료구조) : 순환구조가 없음. 이분그래프가 가능