[백준] 백트래킹 - 13265. 색칠하기(문제 푸는 중)

문제

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

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

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

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

 

입력

입력의 첫 줄에는 테스트 케이스의 개수 T 가 주어진다.

그 다음 줄부터 각 테스트 케이스에 대해 동그라미의 개수 n(n<=1000)과 직선들의 개수 m(m<=100,000)이 주어지고, 그 다음 줄부터 m 줄에 걸쳐 동그라미들이 연결된 직선에 대한 정보가 주어진다. (x y) 로 주어지면 동그라미 x 와 동그라미 y 가 직선으로 서로 연결되었다는 의미이다. 동그라미들의 숫자는 1 부터 n 까지이다.

 

출력

각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다.

 

예제 입력1

3        ----------  개수  ----------
4 5     --- 첫번째 테스트 케이스 ---
1 2
2 3
3 4
1 3
2 4
6 9    --- 두번째 테스트 케이스 ---
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
8 8    --- 세번째 테스트 케이스 ---
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1

 

예제 출력1

impossible

possible

possible

 

생각

어떻게 풀어야 할 지 모르겠어서 결국 스터디 전까지 풀지 못했다. 

푼 사람들 코드를 참고해서 혼자 풀어보도록 해야겠다. 

 

작성한 코드

#include<iostream>
#include<queue>

using namespace std;

int T, n, m;
bool flag;

void dfs(int idx, int cnt,  bool cir[][1001], int* color) {
   if (!flag) {
      return;
   }
   // 색상은 1, 2 두가지 경우
   if (color[idx] == 1) {
      for (int i = 1;i <= n;i++) {
         if (cir[idx][i]) {
            if (color[i] == 1) flag = false;
            else if (color[i] == 0) color[i] = 2;
            else continue;
            dfs(i, cnt + 1, cir, color);
         }
      }
   }
   else if (color[idx] == 2) {
      for (int i = 1;i <= n;i++) {
         if (cir[idx][i]) {
            if (color[i] == 2) flag = false;
            else if (color[i] == 0) color[i] = 1;
            else continue;
            dfs(i, cnt + 1, cir, color);
         }
      }
   }
}


int main(int* argc, char** argv) {
   cin.sync_with_stdio(false);
   cin.tie(0);

   cin >> T;

   for (int i = 0;i < T;i++) {
      cin >> n >> m;
      bool cir[1001][1001] = { false, };
      int color[1001] = { 0, };

      for (int j = 0;j < m;j++) {
         int x, y;
         cin >> x >> y;
         cir[x][y] = true;
         cir[y][x] = true;
      }

      flag = true;

      for (int i = 1;i <= n;i++) {
         bool alone = true;
         for (int j = 1;j <= n;j++) {
            if (cir[i][j]) {
               alone = false;
               break;
            }
         }
         if (!alone) {   // 혼자 동떨어있지 않은 경우 시작. 붙어있는 것들만 고려하면 됨
            color[i] = 1;
            dfs(i, 0, cir, color);
            break;
         }
      }
      
      if (flag) cout << "possible\n";
      else cout << "impossible\n";
   }

   return 0;
}

+) 벡터를 사용한 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
int ch[1001];

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);

   int T,n,m,x,y;
   cin >> T;

   while (T-- > 0)
   {
      int V, E;
      cin >> V >> E;

      vector <int> vc[1002];
      vector <bool> visited(1002, false);
      vector <int> color(1002);

      for (int i = 0; i < E; i++)
      {
         int from, to;
         cin >> from >> to;

         vc[from].push_back(to);
         vc[to].push_back(from);
      }

      int palette;
      bool ch = true;

      for (int i = 1; i <= V; i++)
      {
         if (visited[i]) continue;

         queue<int> q;
         q.push(i);
		 
         // 색상은 -1, 1 두가지
         while (!q.empty())
         {
            int here = q.front();
            q.pop();

            if (visited[here]) continue;
            visited[here] = true;
            if (color[here] == 0)
            {
               color[here] = 1;
               palette = -1;
            }
            else if (color[here] == 1)
               palette = -1;
            else if (color[here] == -1)
               palette = 1;

            for (int i = 0; i < vc[here].size(); i++)
            {
               int next = vc[here][i];
               if (color[next] != 0 && color[next] == -palette)
               {
                  ch = false;
                  break;
               }
               color[next] = palette;
               q.push(next);
            }
            if (!ch) break;
         }

      }
      if (ch) cout << "possible\n";
      else cout << "impossible\n";
   }
   return 0;
}