Difference between r1.1 and the current
@@ -8,32 +8,30 @@
여러 테스트 케이스가 입력될 수 있다. 각 테스트 케이스의 첫째 줄에는 정점의 개수 n(1<n<200)이 입력된다. 각 정점에는 0부터 n-1까지의 번호가 붙는다. 그 다음 줄에는 모서리를 나타내는 두 개의 정점 번호가 들어있다. n자리에 0이 입력되면 입력이 끝난 것이며, 그 줄은 처리하지 않는다.
=== Output ===
입력된 그래프가 두 색으로 칠할 수 있는 그래프인지 판단하고 아래 예에 나온 형식에 맞게 결과를 출력하라.
|| 작성자 || 사용언어 || 개발시간 || 코드 ||
|| [문보창] || C++ || 60min || [Bicoloring/문보창] ||
=== Output ===
입력된 그래프가 두 색으로 칠할 수 있는 그래프인지 판단하고 아래 예에 나온 형식에 맞게 결과를 출력하라.
=== Sample Input ===
{{{~cpp
3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0
}}}
=== Sample Output ===
{{{~cpp
NOT BICOLORABLE.
BICOLORABLE.
}}}
=== Sample Input ===
{{{~cpp
3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0
}}}
=== Sample Output ===
{{{~cpp
NOT BICOLORABLE.
BICOLORABLE.
}}}
=== 풀이 ===|| 작성자 || 사용언어 || 개발시간 || 코드 ||
|| [문보창] || C++ || 60min || [Bicoloring/문보창] ||
About Bicoloring ¶
평면 위에 지도가 있을 때, 각 영역을 인접한 다른 영역과 구분할 수 있게 서로 다른 색으로 칠하고자 한다면, 네 가지 색만 있으면 된다는 4색 정리(four-color theorem)라는 것이 있다. 이 정리는 100년이 넘게 증명되지 않은 채로 남아 있다가 1976년에 컴퓨터의 도움을 받아서 증명될 수 있었다. 여기에서는 조금 더 쉬운 문제를 풀면 된다. 어떤 연결 그래프가 주어졌을 때 그 그래프를 두 색으로 칠할 수 있는지, 즉 모든 정점을 빨간색 또는 검은색으로 칠할 때 인접한 정점이 같은 색으로 칠해지지 않게 할 수 있는지 알아보자. 문제를 간단하게 하기 위해 그래프가 연결 그래프고, 무방향 그래프며, 자체 루프가 없다고(즉(x, x)같이 한 정점에서 출발해서 그 정점으로 바로 연결되는 모서리가 없다고) 가정하자.
Input ¶
여러 테스트 케이스가 입력될 수 있다. 각 테스트 케이스의 첫째 줄에는 정점의 개수 n(1
Output ¶
입력된 그래프가 두 색으로 칠할 수 있는 그래프인지 판단하고 아래 예에 나온 형식에 맞게 결과를 출력하라.
Sample Input ¶
~cpp 3 3 0 1 1 2 2 0 9 8 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0
Sample Output ¶
~cpp NOT BICOLORABLE. BICOLORABLE.
풀이 ¶
| 작성자 | 사용언어 | 개발시간 | 코드 |
| 문보창 | C++ | 60min | Bicoloring/문보창 |
