1824: 두 색 칠하기 (bicoloring)
[만든사람 : ]
문제 설명
평면 위에 지도가 있을 때, 각 영역을 인접한 다른 영역과 구분할 수 있게 서로 다른 색으로 칠하고자 한다면, 네 가지 색만 있으면 된다는 4색 정리라는 것이 있다.
이 정리는 100년이 넘게 증명되지 않은 채로 남아 있다가 1976년에서야 컴퓨터의 도움을 받아서 증명될 수 있었다.
이 문제는 그래프의 정점을 칠하는 문제로 구조화하여 풀 수 있다. 어떤 연결 그래프가 주어졌을 때 그 그래프를 두 색으로 칠할 수 있는지, 즉 모든 정점을 빨간색
또는 검은색으로 칠할 때 인접한 정점이 같은 색으로 칠해지지 않게 할 수 있는지 알아보자.
문제를 단순하게 하기 위해 그래프가 연결 그래프이고 무방향 그래프이며 자체 루프가 없다고 가정하자. 0부터 n-1까지의 n개의 정점과 간선의 수 m이 입력될 때,
2가지 색깔로 칠할 수 있는지 결정하는 프로그램을 작성하시오.
이 정리는 100년이 넘게 증명되지 않은 채로 남아 있다가 1976년에서야 컴퓨터의 도움을 받아서 증명될 수 있었다.
이 문제는 그래프의 정점을 칠하는 문제로 구조화하여 풀 수 있다. 어떤 연결 그래프가 주어졌을 때 그 그래프를 두 색으로 칠할 수 있는지, 즉 모든 정점을 빨간색
또는 검은색으로 칠할 때 인접한 정점이 같은 색으로 칠해지지 않게 할 수 있는지 알아보자.
문제를 단순하게 하기 위해 그래프가 연결 그래프이고 무방향 그래프이며 자체 루프가 없다고 가정하자. 0부터 n-1까지의 n개의 정점과 간선의 수 m이 입력될 때,
2가지 색깔로 칠할 수 있는지 결정하는 프로그램을 작성하시오.
입력 설명
첫째 줄에는 정점의 개수 n(1 ≤ n ≤ 200)과 간선의 수 m이 입력된다.
둘째 줄부터 m줄에 걸쳐서 각 간선이 연결하는 정점의 번호가 공백으로 구분되어 입력된다.
둘째 줄부터 m줄에 걸쳐서 각 간선이 연결하는 정점의 번호가 공백으로 구분되어 입력된다.
출력 설명
입력된 그래프가 두 색으로 칠할 수 있는 그래프인지를 판단하고 아래 예에 나온 형식에 맞게 결과를 출력하라.
입력 예시 Copy
3
3
0 1
1 2
2 0
출력 예시 Copy
IMPOSSIBLE