(Java/자바) - 백준(BOJ) 13265번 : 색칠하기

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

13265번: 색칠하기

---

• 문제 : 

어린 토니킴은 색칠공부를 좋아한다.

 

토니킴은 먼저 여러 동그라미와 동그라미 두 개를 연결하는 직선들 만으로 그림을 그리고 (모든 동그라미들 사이에 직선이 있을 필요는 없다), 연결된 두 동그라미는 서로 색이 다르게 되도록 색을 칠하고자 한다.

 

이 그림을 색칠하는데 필요한 최소의 색의 개수를 구하는 문제는 어렵기 때문에 토니킴은 2 가지 색상으로 색칠이 가능한지의 여부만을 알고 싶어한다.

 

동그라미들의 번호와 동그라미들이 서로 연결된 직선에 대한 정보가 주어졌을 때, 이 동그라미들이 2 가지 색상으로 색칠이 가능한지 알아내자.

 

 

 

---

• 풀이 :

그래프 탐색 문제였습니다.

 

BFS 또는 DFS로 해당 노드를 방문하며 같은 색으로 칠해진 노드끼리 인접했을 경우 impossible을 출력하면 됩니다.

 

풀이입니다.

 

1. 그래프가 연결 리스트라는 보장이 없으므로 모든 방문하지 않은 노드에 대해서 색을 칠해줘야 함

 

2. 방문하지 않은 노드에 대해 BFS 실시

 

3..visited 배열을 int형으로 선언한 뒤 해당 값에 Depth를 넣는다. depth가 홀수, 짝수인 경우를 각각 다른 색이라고 판단하고 진행한다.

 

4. 만약 현재 탐색중인 노드에서 갈 수 있는 노드들이 방문하지 않은 노드인 경우 Depth +1로 진행하고, 만약 이미 방문했다면 현재 탐색중인 노드와 depth의 2로 나눈 나머지가 같은지 판단한다. 만약 같은 색이라면 인접한 노드끼리 같은 색인 것이므로 false를 리턴한다. 

 

 

 

---

• 소스코드 : 

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

public class Main {
	static int TC, N, M;
	static int[] visited;
	static ArrayList<Integer>[] graph;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		TC = Integer.parseInt(br.readLine());
		graph = new ArrayList[1001];
		for (int tc = 0; tc < TC; tc++) { 
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			for (int i = 1; i < N+1; i++) {
				graph[i] = new ArrayList<Integer>();
			}
			visited = new int[N+1];
			for (int i = 0; i < M; i++) { // 그래프 새성 
				st = new StringTokenizer(br.readLine());
				int x,y;
				x = Integer.parseInt(st.nextToken());
				y = Integer.parseInt(st.nextToken());
				graph[x].add(y);
				graph[y].add(x);
			}
			boolean flag = true;// 색칠 가능 여부
			for (int i = 1; i <= N; i++) { // 방문하지 않은 모든 노드에 대해 bfs 실시 
				if(visited[i] == 0) flag &= bfs(i);
				if(!flag) break;
			}
			if(flag) System.out.println("possible");
			else System.out.println("impossible");
		}
		
	}
	private static boolean bfs(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(start);
		visited[start] = 1;
		while(!q.isEmpty()) {
			int curr = q.poll();
			for (int next : graph[curr]) {
				if (visited[next] == 0) {
					q.add(next);
					visited[next] = visited[curr] + 1;
				}else if (visited[next] %2 == visited[curr]%2) { // 인접한 노드가 이미 같은 색으로 칠해져있다면 종료					return false;
				}
			}
		}
		return true;
	}
}