백준 - 13265 색칠하기

문제

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

13265번: 색칠하기

그래프를 2가지 색으로 색칠하는 문제였는데, 서로 연결된 두 노드를 다른 색으로 칠할 수 있는지의 여부를 구하는 문제였다.

 

문제 풀이

그래프를 만들고 dfs로 모든 노드를 탐색하면서 색을 바꿔주면서 풀었다.

dfs

• 현재 노드가 아직 색칠이 되지 않았으면 1로 색칠해준다.
• 현재 노드와 연결된 노드들을 탐색한다
  • 다음 노드의 색이 없으면 방문 전이기 때문에 현재 노드 색과 다른 색으로 칠해주고 방문한다.
  • 다음 노드의 색이 있다면
    • 현재 노드의 색과 동일하면 impossible!
    • 현재 노드의 색과 다르고 방문 전이면 방문해준다.

모든 노드를 방문한 후에도 isPossible이 true라면 가능, flase면 불가능을 출력하면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <vector>

using namespace std;

int N,M;
int color[1001] = {0}; //0: 색칠안됨  1: 색1  2: 색2
bool isPossible = true;
int visit[1001] = {0};
vector<vector<int>> G(1001);

int findNextColor(int nowColor){
    if(nowColor == 1) return 2;
    else return 1;
}

void dfs(int n){
    
    if(color[n] == 0){ //아직 색칠 안됨 (맨 처음 노드)
        color[n] = 1;
    }
    
    int nowColor = color[n];
    int mustNextColor = findNextColor(nowColor);
    visit[n] = 1;
    
    for(int i=0;i<G[n].size();i++){
        int nextNode = G[n][i];
        int nextColor = color[nextNode];
        
        if(nextColor == 0){ //방문x, 색칠하면 됨
            color[nextNode] = mustNextColor;
            dfs(nextNode);
        }        
        else{
            if(nowColor == nextColor){ //불가능
                isPossible = false;
                return;
            }
            else { //가능, 방문 안했으면 dfs
                if(visit[nextNode] == 0) dfs(nextNode);
            }
        }        
    }
}

int main(int argc, char** argv)
{
    int T;
    scanf("%d",&T);        
    
   while(T--){
       scanf("%d %d",&N,&M);
       fill(&G[0], &G[1001], vector<int>(0));
       fill(color, color+1001, 0);
       fill(visit, visit+1001, 0);
       isPossible = true;
       
       for(int i=0;i<M;i++){
           int a,b;
           scanf("%d %d", &a, &b);
           G[a].push_back(b);
           G[b].push_back(a);
       }
       
       for(int i=1;i<=N;i++){
           if(visit[i] == 0) dfs(i);
           if(!isPossible) break;
       }
       
       if(isPossible) printf("possible\n");
       else printf("impossible\n");
   }
	return 0;
}