[백준] 단계별로 풀어보기(단계:24, DFS와BFS,JAVA)1707번, 이분 그래프

문제 링크

1707번: 이분 그래프

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

DFS(깊이 우선 탐색)은 아래 그림처럼 어떤 조건을 가지고 목표노드에 도달하기까지 자식노드를 통해 이동하며 목표노드까지 도달하는 것을 말합니다.

자식 노드에 도착하면 그 자식노드에서 조건에 만족하는 자식노드로 다시 이동하여 목표 노드로 이동합니다.

 

출처 : https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

DFS

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

BFS

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이분 그래프란?

인접한 정점을 다른색으로 서로 다른색으로 칠해도 모든 정점을 2가지 색으로 칠할 수 있는 그래프입니다.

https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84

더 자세한 내용은 링크를 남겨두겠습니다.

이분 그래프 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 이분 그래프로 나누었을 때 각 집합의 정점들은 인접하지 않아야 한다.

2. 인접하면 YES, 인접하지 않으면 NO를 결과로 출력해야 한다.

 

저는 BFS(너비우선탐색)을 이용하여 문제를 해결하였습니다.

이분 그래프를 위해 저는 색깔이 아닌 1팀과 -1팀으로 나누어서 확인을 하였습니다.

 

1팀과 -1팀으로 나눈 이유는 인접한 정점을 다른 색깔로 표현할 때 -1만 곱해주면 변경이 가능하기 때문입니다.

 

그래프에 대한 내용을 정의하기 위해 ArrayList<ArrayList<Integer>>의 형태로 리스트를 만들어주었습니다.

위와 같이 정의하여 데이터를 저장하면 각 정점이 어떤 정점으로 이동하는지 간단하게 저장할 수 있습니다.

예를 들어 

1 -> 4

1 -> 3

2 -> 5

3 -> 4

ArrayList<ArrayList<Integer>>의 저장되는 모습은 리스트 안에 리스트가 포함되는 형식으로 저장됩니다.

정점
1	3	4
2	5
3	1	4
4	1	4
5	2

 

그래프의 값을 리스트에 저장하였다면 각 정점을 기준으로 BFS탐색을 통해 팀을 나누어보도록 하겠습니다.

set배열을 통해서 현재 무슨 집합인지 나누었습니다.

 

-1 = 레드팀

0 = 무소속

1 = 블루팀

 

예제 입력1에서 첫 번째 테스트케이스의 그래프를 표로 확인하며 보여드리겠습니다.

아래는 예제로 주어진 그래프입니다.

그래프의 내용이 저장된 ArrayList<ArrayList<>>의 해당하는 표

정점
1	3
2	3
3	1	2

1. 정점 1부터 범위 탐색을 진행합니다.

우선 정점의 기본적인 팀은 블루팀(1팀)으로 설정하였습니다.

 

정점1 블루팀이 된 후 BFS와 그래프 내용인 ArrayList<ArrayList<Integer>>을 이용하여 인접한 정점을 탐색합니다.

 

그래프에서 정점1과 인접한 정점은 3으로 빨간팀(-1팀)을 배정합니다.

 

BFS에 사용되는 큐에는 인접한 정점을 저장하기 때문에 큐에는 3을 저장합니다.

2. 큐에 저장된 정점 3을 꺼내서 인접한 정점의 팀을 결정합니다.

정점 3은 빨간팀(-1팀)이 되어있기 때문에 기본팀인 파란팀(1팀)으로 설정할 필요는 없습니다.

정점 3에 인접한 정점을 탐색하였을 때 인접한 정점 2를 발견합니다.

정점 2는 정점 3에 반대팀으로 가야하기 때문에 블루팀(1팀)이 됩니다.

큐에는 인접한 정점은 1과 3이지만 1은 탐색을 하여서 팀이 정해져있기 때문에 정점 2만 저장합니다.

3. 큐에 저장된 정점 2을 꺼내서 인접한 정점의 팀을 결정합니다.

정점 2는 파란팀(1팀)이 되어있기 때문에 따로 기본팀을 설정할 필요는 없습니다.

인접한 정점 3은 팀이 정해져있기 때문에 탐색가능하지 않기 때문에 BFS탐색을 종료합니다.

4. 현재 탐색한 그래프와 떨어진 정점이 있을 수 있으니 남은 정점들을 확인할 때 탐색해야 합니다.

현재 모든 정점이 탐색되었기 때문에 탐색을 진행하지 않습니다.

5. 해당 그래프의 탐색이 종료되었기 때문에 이분 그래프이면 YES, 아니면 NO를 출력합니다.

 

5번째 과정에서 이분 그래프를 확인하기 위해서 BFS탐색시 인접한 정점이 같은 색이면 탐색을 종료하고 NO를 출력하도록 하였습니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 그래프에 대한 정보를 ArrayList<ArrayList<Integer>>에 저장합니다.

2. BFS(너비 우선 탐색)을 이용하여 1~V까지 정점을 탐색합니다.

3. 인접한 정점은 해당 정점의 반대팀으로 설정합니다.

4. 모든 탐색이 종료되면 이분 그래프인지 YES, NO로 결과를 출력합니다.

 

※정점의 팀이 정해지지 않았을 때 기본팀은 블루팀(1팀)으로 설정하였습니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 그래프에 대한 정보를 저장하였습니다.
• 그래프에 내용 저장할 ArrayList<ArrayList<Integer>> graph를 만들었습니다.
• BFS로 그래프의 인접한 정점과 팀을 구하는 구하는 bfs 함수를 만들었습니다.
• BufferedWriter에 이분 그래프을 확인하여 YES or NO을  저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs은 set[], graph와 Queue를 통해 인접한 정점에 팀을 탐색하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int K,V,E;
	public static String result;
	public static int[] set;		//정점 팀 설정 배열
	public static ArrayList<ArrayList<Integer>> graph;	//그래프 내용 저장 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //---------입력값 저장 및 리스트 초기화-----------
    	StringTokenizer st;
    	K = Integer.parseInt(br.readLine());
    	for(int i=0;i<K;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		V = Integer.parseInt(st.nextToken());
    		E = Integer.parseInt(st.nextToken());
    		set = new int[V+1];
    		graph = new ArrayList<>();
    		result = "YES";
    		for(int j=0;j<=V;j++) 
    			graph.add(new ArrayList<>());
    		
    		for(int j=0;j<E;j++) {
    			st = new StringTokenizer(br.readLine()," ");
    			int row = Integer.parseInt(st.nextToken());
    			int col = Integer.parseInt(st.nextToken());
    			graph.get(row).add(col);
    			graph.get(col).add(row);
    		}
    		for(int j=1;j<=V;j++) {		//1~V 탐색
    			if(set[j] == 0) {	//팀 정해지지 않은 정점 탐색
        			if(!bfs(j)) {	//BFS 탐색
        				result = "NO";
        				break;
        			}
    			}
    		}
    		bw.write(result + "\n");		//이분 그래프 BufferedWriter 저장
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //-----------BFS을 통해 인접한 정점 탐색 함수----------
    public static boolean bfs(int point) {
    	Queue<Integer> queue = new LinkedList<Integer>();
    	queue.add(point);
    	set[point] = 1;		//기본팀(블루팀, 1팀) 설정
    	while(!queue.isEmpty()) {
    		int p = queue.poll();
    		for(Integer value : graph.get(p)) {
    			if(set[value] == set[p]) {
    				return false;	//인접 정점 같은팀일 때
    			}
    			if(set[value]==0) {
    				set[value] = set[p] * -1;	//인접 정점 반대팀 설정
    				queue.add(value);
    			}
    		}
    	}
    	return true;
    }
}