백준 13265 : 색칠하기

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

13265번: 색칠하기

 

koi 색칠하기에서 살짝만 바뀐 문제.

 

#include <iostream>
#include <vector>
 
int T, n, m;
 
std::vector<std::vector<int>> vec;
int visited[1001];
 
bool chk_visit[1001];
 
void input()
{
    std::cin >> n >> m;
    vec = std::vector<std::vector<int>>(n);
    int first, second;
    for (int i = 0; i < m; ++i)
    {
        std::cin >> first >> second;
        //연결된 정점들을 반열린구간으로 맞춰주기 위해 --
        --first;
        --second;
        vec[first].push_back(second);
        vec[second].push_back(first);
    }
}
 
void output(bool ans)
{
    if (ans == 0)
    {
        std::cout << "impossible\n";
    }
    else
    {
        std::cout << "possible\n";
    }
    return;
}
 
void dfs_visit(int vertex, int color)
{
    //이 정점에 방문했었다.
    chk_visit[vertex] = true;
    visited[vertex] = color;
    int can = 1;
    for (int i = 0; i < vec[vertex].size(); ++i)
    {
        //해당 정점(vec[vertex][i])에 연결되어있는 다른 정점들을 순회하는
        //i를 둘러보면서, 연결되어있는 다른 정점들이 color로 칠해져있는지
        //visited[vertex에 연결된 다른 정점들]을 확인하면서
        //만약 칠이 되어 있다면 문제 조건에 의해 인접한 같은 색이 되므로
        //빠꾸를 먹여야 하니 플래그 can을 0으로 만들어주자.
        if (visited[vec[vertex][i]] == color)
        {
            can = 0;
        }
    }
    if (can == false)
    {
        //하지만 이 정점은 색칠이 불가능한 정점.
        //따라서 방문은 했으나 색칠은 못하게 됨
        //chk_visit[vertex] = false; 가 여기에 없는 이유
        visited[vertex] = 0;
        return;
    }
    for (int i = 0; i < vec[vertex].size(); ++i)
    {
        //이미 위에서 색칠이 가능한 정점에 대해 검증을 마친 상태
        //따라서 재귀를 호출하는데 필요한 조건은
        //해당 정점을 이미 접근했는가? 뿐이다
        if (visited[vec[vertex][i]] == 0)
        {
            dfs_visit(vec[vertex][i], 1);
        }
        //따라서 1을 이미 칠했고, 그 정점이 올바른 색을 칠한거라면
        //visited[vec[vertex][i]]는 0이 아닐 것.
        //만약 0이라면 위의 검증 코드에서 빠꾸를 먹었을테니 2를 칠해주면 된다.
        if (visited[vec[vertex][i]] == 0)
        {
            dfs_visit(vec[vertex][i], 2);
        }
    }
}
 
void solve()
{
    for (int i = 0; i < n; ++i)
    {
        if (visited[i] != 0)
        {
            continue;
        }
 
        dfs_visit(i, 1);
 
        for (int j = 0; j < n; ++j)
        {
            //i가 n까지 도는데, 초기화하지 않는다면
            //색칠할 수 없어 그대로 놔둔 visited[j]가
            //방문했던 모든 정점을 기록한 chk_visit[j]에 걸려
            //output(false)를 호출하게 될 것이다.
            if (chk_visit[j] != false && visited[j] == 0)
            {
                output(false);
                return;
            }
        }
    }
    output(true);
    return;
}
 
void clear()
{
    vec.clear();
    for (int i = 0; i < n; ++i)
    {
        visited[i] = 0;
        chk_visit[i] = false;
    }
}
 
int main()
{
    std::cin.tie(0);
    std::cin.sync_with_stdio(false);
    std::cout.tie(0);
    std::cout.sync_with_stdio(false);
    
    std::cin >> T;
    for (int i = 0; i < T; ++i)
    {
        input();
        solve();
        clear();
    }
    return 0;
}

색칠하는 부분은 내가 직접 다 짠건 아니고... 교재 보고 확인해서 좀 바꿨다.

 

내가 생각해서 짜본것도 얼추 맞을것같다는 생각은 드는데, 인접리스트가 아니라 인접 행렬이기도 하고

 

또 틀리면 한참 삽질할것같고 그래서... 아이고야

 

이게 참, 그렇구만