[Baekjoon] 13265_색칠하기

Gold V

문제(출처: https://www.acmicpc.net/problem/13265)

---

< 색칠하기 >

 

문제 풀이

 

bfs를 활용하면서 전 동그라미와 다른 색을 칠할 수 있는지 없는지를 판별한다.

 

 

 

 my solution (Java)

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 _13265_ { // 색칠하기
	static ArrayList<ArrayList<Integer>> arr;
	static int check[];
	static boolean flag;
	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int t=Integer.parseInt(bf.readLine());
		for(int i=0; i<t; i++) {
			st=new StringTokenizer(bf.readLine());
			
			int n=Integer.parseInt(st.nextToken()); // 동그라미 개수
			int m=Integer.parseInt(st.nextToken()); // 직선 개수
			
			arr=new ArrayList<>();
			check=new int[n];
			flag=false;
			for(int j=0; j<n; j++) {
				arr.add(new ArrayList<>());
				check[j]=-1;
			}
			
			for(int j=0; j<m; j++) {
				st=new StringTokenizer(bf.readLine());
				int x=Integer.parseInt(st.nextToken())-1;
				int y=Integer.parseInt(st.nextToken())-1;
				arr.get(x).add(y);
				arr.get(y).add(x);
			}
			
			for(int j=0; j<n; j++) {
				if(check[j]==-1) {
					check[j]=0;
					bfs(j);
				}
			}	
			if(flag) System.out.println("impossible");
			else System.out.println("possible");
		}
	}
	private static void bfs(int j) {
		Queue<Integer>queue=new LinkedList<>();
		queue.add(j);
		
		while(!queue.isEmpty()) {
			int num=queue.poll();
			for(int i=0; i<arr.get(num).size(); i++) {
				if(check[arr.get(num).get(i)]==-1) {
					if(check[num]==0) {
						check[arr.get(num).get(i)]=1;
						queue.add(arr.get(num).get(i));
					}
					else if(check[num]==1) {
						check[arr.get(num).get(i)]=0;
						queue.add(arr.get(num).get(i));
					}
				}else if(check[arr.get(num).get(i)]==0) {
					if(check[num]!=1) {
						flag=true;
						return;
					}
				}else if(check[arr.get(num).get(i)]==1) {
					if(check[num]!=0) {
						flag=true;
						return;
					}
				}
			}
		}
	}
}

 

Main

- 테스트 케이스 개수(t) 입력

- 동그라미 개수(n), 직선들의 개수(m) 입력

- arr : 인접 리스트

  check : 동그라미 색상

   flag : 색칠 가능 여부

- 직선들의 개수(m) 만큼 입력하여 인접 리스트 정보 저장

- 동그라미 전체를 탐색하며 아직 색칠하지 않은 동그라미인 경우 색칠 후 bfs 함수 호출

- flag 값에 따라 result 출력

 

bfs

- queue에 동그라미 시작 번호 저장

- queue가 빌 때까지 반복 -> 현재 동그라미와 인접된 동그라미를 탐색 -> 인접된 동그라미가 아직 색칠하지 않은 동그라미(값이 -1)라면 현재 동그라미와 다른 색으로 색칠 후 queue에 저장 / 인접된 동그라미가 이미 색칠된 동그라미라면 현재 동그라미와 다른 색인지 판별. 같은 색이라면 flag를 true로 저장 후 종료

 

---

생각🤔

 

---