[JAVA]BOJ(백준) - 이분 그래프 - 1707

문제내용

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

1707번: 이분 그래프

 

---

문제 접근 방법

처음에 풀때는 간선의 존재여부를 1로 표시해주는 인접행렬을 이용한 BFS방식으로 풀었다.

그결과 시간초과가 나는 풀이가 됐고, 간선을 표시해주는 방법을 찾아보니

인접행렬 대신 ArrayList<ArrayList<Integer>> 를 사용하는 방법이 있다는 것을 알았다.

 

간단히 예를 들면 ArrayList<ArrayList<Integer>> map = new ArrayList<ArrayList<>>(); 가 있을때

map에 ArrayList<Integer>를 add했다는 가정하에

 

v1과 v2 사이에 간선이 있을때

v1=5, v2=7 을 입력한다면

 

map.get(v1).add(v2);

map.get(v2).add(v1);

 

으로 사용 할수 있다. 

이때 System.out.print(map.get(v1)+" "+map.get(v2)); 를 하면

값은 [7] [5] 가 나오게된다.

 

이렇게 인접행렬대신 정점 사이에 간선이 있을경우를 표현할수 있게된다.

자세한 내용은 코드를 참고하면 좋을것 같다.

 

---

 

풀이

BFS

public static boolean bfs(int v1) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(v1); //첫 정점 추가
		checkNode[v1]=1; //첫 정점 방문(1로 색칠)
		
		while(!queue.isEmpty()) {
			int v = queue.poll();
		
			for(int i:map.get(v)) { //정점 v에 연결된 정점을 i에 할당
				//정점 v일때 방문배열값과 정점 i일때 방문배열값이 같으면 이분그래프아님.
				if(checkNode[v]==checkNode[i]) {
					ans = "NO";
					return false;
				}
				//정점i가 방문배열값이 0이면 색칠 해줘야함.
				if(checkNode[i]==0) {
					//v에 연결된 i를 v와는 다른색으로 칠하기위해 -1를 곱함.
					checkNode[i] = checkNode[v]*-1;  
					queue.add(i); //정점 i를 큐에 추가
				}
			}
		}
		return true;
	}

---

전체 코드

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 Main {
	static int K; // 테스트 케이스
	static int V, E; // 정점, 간선
	static int[] checkNode; // 정점 방문배열(1, -1로 색을 표현함)
	static ArrayList<ArrayList<Integer>> map; // 간선존재 여부표시할 리스트(인접 행렬이라고 생각)
	static String ans; // YES 나 NO를 넣을 변수
	static ArrayList<String> result = new ArrayList<String>(); // 확인된 그래프에 대해 ans의 값을 넣어줄 리스트
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		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());
			checkNode = new int[V+1];// 정점번호 1부터 시작해서 크기를 V+1로 만듦
			map = new ArrayList<ArrayList<Integer>>();
			
			//정점 V까지 간선 존재여부를 확인하기 위해 V를 포함.
			//포함 안하면 밑에 map에 간선 여부 확인하기 위해서 정점 V(마지막 정점)를 넣을때 예외 발생
			for(int j=0; j<=V; j++) {
				map.add(new ArrayList<Integer>());
			}
			
			int v1, v2;
			ans = "YES"; // ans를 테케마다 YES로 초기화
			for(int j=0; j<E; j++) {
				st = new StringTokenizer(br.readLine());
				v1 = Integer.parseInt(st.nextToken());
				v2 = Integer.parseInt(st.nextToken());
				map.get(v1).add(v2); //입력값 v1정점과 v2정점 사이에 간선이있을때
				map.get(v2).add(v1); //무방향이라 반대도 성립
			}
			
			
			//정점번호 1~V까지 돌리면서 정점 k의 방문배열 값이 1 or -1이 아닌경우
			//bfs(k)가 false이면 이분그래프 아니라서 break로 for문 탈출
			//for문을 통해 1~V까지 확인하는 이유는 비연결 그래프일 경우도 고려.
			for(int k=1; k<=V; k++) {
				if(checkNode[k]==0) {
					if(!bfs(k)) {
						break;
					}
				}
			}
			
			result.add(ans); //값추가
		}
		
		for(String r:result) {//출력
			System.out.println(r);
		}
		
	}//main
	
	public static boolean bfs(int v1) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(v1); //첫 정점 추가
		checkNode[v1]=1; //첫 정점 방문(1로 색칠)
		
		while(!queue.isEmpty()) {
			int v = queue.poll();
		
			for(int i:map.get(v)) { //정점 v에 연결된 정점을 i에 할당
				//정점 v일때 방문배열값과 정점 i일때 방문배열값이 같으면 이분그래프아님.
				if(checkNode[v]==checkNode[i]) {
					ans = "NO";
					return false;
				}
				//정점i가 방문배열값이 0이면 색칠 해줘야함.
				if(checkNode[i]==0) {
					//v에 연결된 i를 v와는 다른색으로 칠하기위해 -1를 곱함.
					checkNode[i] = checkNode[v]*-1;  
					queue.add(i); //정점 i를 큐에 추가
				}
			}
		}
		return true;
	}
}

 

---

마치며

나는 BFS 방식으로만 풀었지만 이문제는 DFS 방식으로도 풀수있기 때문에 DFS 방식으로도 풀어본다면 좋을것 같다.

그리고 인접행렬대신 ArrayList<ArrayList<>> 를 공부할수 있는 문제였다.