[BaekJoon] 백준 1707번 _ 이분 그래프 for JAVA _ DFS, BFS 알고리즘

 

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

1707번: 이분 그래프

 

 

 

문제

 

 

 

---

 

문제 설명이 참 불친절하다.

 

 

이분 그래프는 1 - 2 - 3 으로 연결되어 있는 그래프가 있다고 쳤을 때

 

1과 3이 연결되어있지 않은 그래프를 말한다.

 

 

 

 

 

 

 

 

이렇게 인접한 꼭짓점을 빨, 검으로 칠했을 때 빨빨과 검검이 연결되지 않은 그래프이다.

 

 

 

푼 방법은

 

 

예를 들어 예시를 보면

 

3 2

1 3

2 3

 

일케 되어있음. 그러면 간선이 1 - 3 - 2 로 연결되어있다고 보면 됨.

 

 

 

이렇게 연결이 되어있다고 보면 됨. 나는 2중 arraylist를 사용할거임

 

 

그래서 코드의 36번째 ~ 40번째 줄처럼 나타내야함 이건 알거고

 

 

visited[]라는 배열을 만들어서 1은 1, 3은 -1 이런식으로 인접한 점들에게 1과 -1을 번갈아 넣을 것이다.

 

 

DFS로 넣다가 1이 있는 자리에 -1을 넣으려고 할 때 이 친구가 이분 그래프가 아니게 되는 것이다.

 

 

 

 

코드로 살펴보자

 

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


public class Baek1707 { // 이분 그래프
	public static ArrayList<ArrayList<Integer>> arrayList = new ArrayList<ArrayList<Integer>>();
	public static int[] visited;
	public static boolean ans = false;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int K = Integer.parseInt(br.readLine());
		String[] answer = new String[K]; // 답 출력할 배열
		int index = 0; // 답 출력할 배열의 인덱스
		
		while(K-- > 0) {
			ans = false; // 여러번 돌아야하니까 초기화
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int V = Integer.parseInt(st.nextToken());
			int E = Integer.parseInt(st.nextToken());
			
			visited = new int[V + 1];
			arrayList = new ArrayList<ArrayList<Integer>>();
            		// 얘네 두개도 여러번 돌아야하니까 초기화 해줘야한다. 중요!
			
			for(int i = 0; i <= V; i++)
				arrayList.add(new ArrayList<Integer>());
			
			while(E-- > 0) {
				st = new StringTokenizer(br.readLine(), " ");
				int in1 = Integer.parseInt(st.nextToken());
				int in2 = Integer.parseInt(st.nextToken());
				
				arrayList.get(in1).add(in2);
				arrayList.get(in2).add(in1);
			}
			
			// 간선을 하나씩 살펴보자..
			for(int i = 1; i <= V; i++)
				if(visited[i] == 0) dfs(i, 1); // 처음에 1을 넣는다.
			
			
			if(ans) answer[index] = "NO";
			else answer[index] = "YES";
			index++;
			
		}
		for(String i : answer)
			System.out.println(i);
		
	}
	public static void dfs(int x, int y) { // x는 visited[]의 index이고, y는 넣어줄 값이다.(1아니면 -1)
		visited[x] = y; // 대입
		if(ans) return; // ans = true이면 더이상 확인 안해도 된다.
		
		for(int i = 0; i < arrayList.get(x).size(); i++) {
			int z = arrayList.get(x).get(i);
			if(visited[x] == visited[z]) { // 얘가 연결된 꼭짓점의 값이 겹칠 때이다.
				ans = true;
				return;
			}
			if(visited[z] == 0) // 0일 때 -1을 대입하면서 다시 돌아준다.
				dfs(z, y * -1);
                
            		// visited[] = 1인 곳에 1을 넣거나 하는 경우는 그냥 지나간다.
		}
	}

}

 

 

 

 

성능

 

 

 

어려운 문제였다... 초기화 안해줘서 여러번 틀림 ㅎㅎ

 

 

 

 

 

보통 BFS로 푸는 것 같아서 BFS로도 풀어보겠다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Baek1707_BFS { // BFS
	public static ArrayList<ArrayList<Integer>> arrayList = new ArrayList<ArrayList<Integer>>();
	public static int[] visited;
	public static boolean ans = false;
	public static String answer[];
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int K = Integer.parseInt(br.readLine());
		String[] answer = new String[K];
		int index = 0;
		
		while(K-- > 0) {
			ans = false;
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int V = Integer.parseInt(st.nextToken());
			int E = Integer.parseInt(st.nextToken());
			
			visited = new int[V + 1];
			arrayList = new ArrayList<ArrayList<Integer>>();
			
			for(int i = 0; i <= V; i++)
				arrayList.add(new ArrayList<Integer>());
			
			while(E-- > 0) {
				st = new StringTokenizer(br.readLine(), " ");
				int in1 = Integer.parseInt(st.nextToken());
				int in2 = Integer.parseInt(st.nextToken());
				
				arrayList.get(in1).add(in2);
				arrayList.get(in2).add(in1);
			}
			for(int i = 1; i <= V; i++)
				if(visited[i] == 0)
					bfs(i);
					
			if(ans) answer[index] = "NO";
			else answer[index] = "YES";
			index++;
			
		}
		for(String i : answer)
			System.out.println(i);
	}
	
	public static void bfs(int n) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(n);
		visited[n] = 1;
		
		while(!q.isEmpty()) {
			int index = q.poll();
			
			for(int i = 0; i < arrayList.get(index).size(); i++) {
				int z = arrayList.get(index).get(i);
				if(visited[z] == 0) {
					visited[z] = visited[index] * -1;
					q.add(z);
				}
				
				if(visited[index] == visited[z]) {
					ans = true;
					return;
				}
			}
		}
			
	}
}

 

 

 

 

BFS 성능

 

 

 

 

 

DFS가 미세하게 시간 효율이 낫다.