[BOJ] 백준 13265 색칠하기 (JAVA)

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

13265번: 색칠하기

 

 

🔍 Solve

SWEA와 문제 유형이 비슷하게 제일 먼저 테스트 케이스의 개수가 주어집니다.

해당 입력을 테스트케이스별로 나누면 아래 그림과 같이 예제를 나눌 수 있습니다.

이 중 테스트케이스 1번을 그래프로 그려 두 가지 색으로 칠해보면 다음과 같이 불가한 경우를 찾을 수 있습니다. 

따라서 문제를 해결하기위해 color 일차원 배열을 사용하였습니다.

두 가지 색의 예시를 빨간색과 파란색이라고 해봅시다.

color배열의 값이 0이면 노드 4번과 같이 칠해지지 않은 상태, 1이면 빨간색, -1이면 파란색을 나타내도록 했습니다.

이때, 칠해지지 않은 상태인 0은 아직 방문하지 않았다는 의미 또한 가지고 있습니다.

 

각 노드에서부터 연결되어있는 노드들을 저장하기 위해 List 배열을 사용했습니다.

노드 전체를 탐색하며 아직 방문하지 않은(color배열의 값이 0인) 지점이 있다면, 임의로 빨간색(1)으로 채우고 dfs를 돌며 나머지 노드의 색을 칠합니다.

 

dfs에서는 각 노드에 연결되어있는 노드를 하나씩 꺼내와 탐색합니다.

현재 노드가 바로 전 노드와 같은 색이라면 전역변수인 isPossible을 false로 설정하고 return 합니다.

color[현재노드]가 0으로, 아직 방문하지 않은 곳이라면 color[전 노드]의 반대색을 칠하고 현재 노드를 기준으로 다시 dfs를 돌게 됩니다.

 

만약 dfs를 도는 중간에 return하여 isPossible가 false값을 가지고 있다면 "impossible"을 출력하고,

모든 dfs를 다 돈 후 빠져나왔다면 "possible"을 출력합니다.

 

❗ Code

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

public class Main {

    static int N;  //동그라미 개수
    static int M;  //직선의 개수
    static int[] color;
    static List<Integer>[] list;
    static boolean isPossible;

   public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for(int t=1;t<=T;t++){
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            color = new int[N+1];
            list = new List[N+1];
            isPossible = true;

            for(int i=0;i<list.length;i++){
                list[i] = new ArrayList<>();
            }

            for(int i=0;i<M;i++){
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());

                //양방향 연결
                list[from].add(to);
                list[to].add(from);
            }


            for(int i=1;i<=N;i++){
                if(color[i]==0){
                    color[i] = 1;
                    dfs(i);
                }
            }

            if(isPossible) sb.append("possible\n");
            else sb.append("impossible\n");


        }

       System.out.println(sb);

    }


    private static void dfs(int depth){
        for(int i=0;i<list[depth].size();i++){
            int cur = list[depth].get(i);  //각 노드에 연결되어있는 노드

            if(color[cur]==color[depth]){  //현재 노드가 depth노드와 같으면 색이 똑같은 경우다.
                //색이 똑같으면 impossible
                isPossible = false;  //불가능 표시
                return;
            }else if(color[cur]==0){
                //아직 방문 안한곳이면
                color[cur] = color[depth]*-1;  //depth와 반대의 색상 넣어줌
                dfs(cur);
            }
        }
   }
}