문제
2색 칠하기란, 다음 두 조건을 만족하면서 그래프의 정점을 모두 색칠할 수 있는지 묻는 문제이다. 2개의 색이 존재한다. 인접한 두 정점은 색깔이 다르다. 그래프가 주어질 때, 2색 칠하기가 가능한지 출력하는 프로그램을 작성하시오. 예를 들어, 아래의 그래프는 2색 칠하기가 가능한 그래프이며, 정점을 색칠한 결과는 다음과 같다.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 10,000, 1 ≤ M ≤ 100,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b로 이루어져 있으며, 이는 정점 a와 정점 b가 연결되어 있다는 의미이다.(0 ≤ a, b ≤ N-1)
출력
주어진 그래프에 대하여 2색 칠하기를 할 수 있으면 YES, 할 수 없으면 NO를 출력한다.
예제 입력
9 10
0 1
0 2
0 3
1 5
2 5
3 4
5 6
5 8
6 7
7 8
예제 출력
YES
예제 입력
9 11
0 1
0 2
0 3
1 5
2 5
3 4
4 5
5 6
5 8
6 7
7 8
예제 출력
NO
#코드(dfs)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
import sys
#2개의 색이 존재한다. 인접한 두 정점은 색깔이 다르다.
def dfs(x, c):
global myGraph, check, flag
check[x] = c
for i in range(len(myGraph[x])):
x2 = myGraph[x][i]
if check[x2] != 0 and check[x2] == c:
flag = False
return
if c == 1: c2 = -1
else: c2 = 1
if check[x2] == 0:
dfs(x2, c2)
if __name__ == "__main__":
myGraph = {}
flag = True
check = [0]*100000
n, m = map(int, sys.stdin.readline().split())
for i in range(m):
a, b = map(int, sys.stdin.readline().split())
try: myGraph[a].append(b)
except:
myGraph[a] = list()
myGraph[a].append(b)
try: myGraph[b].append(a)
except:
myGraph[b] = list()
myGraph[b].append(a)
dfs(0, 1)
if flag: print('YES')
else: print('NO')
|
cs |
# 접근법
우선 문제의 골자는 현재 정점과 주변 정점과 색이 달라야하고 색은 두 가지의 색만 칠할 수 있다. 이다.
visited 변수는 0, 1, -1 이렇게 3개의 값을 갖는데 0은 아직 어떠한 색도 칠해지지 않았을 경우를 의미하고,
-1과 1은 두 개의 색을 의미한다. 즉 이웃하는 정점과는 1, -1 서로 다르게 값이 맵핑돼 있어야 한다.
dfs(x, c) 메서드를 정의해보자
dfs 메서드는 탐색을 하면 정점의 색을 칠하는 것이고, 칠하는 도중 이웃 정점과 색이 일치하는 경우 더이상 탐색을 진행하지 않고 탐색을 종료하는 기능을 가졌다.
파라미터는 x와 c가 있는데, x는 인덱스를 의미하고, c는 인덱스 x에 들어갈 색상을 뜻한다.
그래서 visited[x] = c 를 통하여 현재 위치에 색상값을 넣어준다.
처음시작은 visited[0] = 1 이다.
그 다음 해당 인덱스의 정점과 이어진 이웃 정점들을 모두 탐색한다.
이웃정점들의 값은 myGraph[x] 가 가지고 있다.
반복문을 통해 하나씩 방문을 해준다.
이웃 정점 하나씩 요부분은 "x2=myGraph[x][i]"에 있다.
여기서 다시 정리를 해보자면 x는 현재의 정점의 인덱스이고, x2는 현재 정점의 이웃 정점의 인덱스인 것이다.
그렇다면 현재 정점의 색상과 이웃정점의 색상을 비교해볼 수 있을 것이다.
현재정점의 색상은 파라미터 c가 들고있다. 그렇다면 이웃정점이 만약 칠해져있다면 이웃정점의 색상은 visited[x2]가 들고 있을 것이다. 즉 결과적으로 visited[x2]!=0 이면서 visited[x2]==c 라는 뜻은 현재 정점과 이웃 정점의 색상이 갔다는 것이고 그렇다면 더 이상 순회를 하는 것은 무의미 해지기 때문 탐색을 종료한다.
만약 색상이 다르다면
이웃 정점의 색상 값을 가지는 c2변수에 현재 정점의 생상 값을 가지는 c의 반대 부호의 값을 넣어주면된다.
if c == 1: c2 = -1
else: c2 = 1
코드로는 이렇게 표현된다.
그러고 만약 이웃정점의 색상이 칠해 지지 않았다면 탐색을 계속하면되는 것이다.
if visited[x2] == 0:
dfs(x2, c2)
# 복습
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
import sys
def dfs(x, c):
global myGraph, visited, flag
visited[x] = c
for i in range(len(myGraph[x])):
x2 = myGraph[x][i]
if visited[x2] != 0 and visited[x2] == c:
flag = False
return
if c == 1: c2 = -1
else: c2 = 1
if visited[x2] == 0:
dfs(x2, c2)
if __name__ == "__main__":
input = sys.stdin.readline
flag = True
n, m = map(int, input().split())
myGraph = [[] for _ in range(n)]
visited = [0]*n
for _ in range(m):
a, b = map(int, input().split())
myGraph[a].append(b)
myGraph[b].append(a)
dfs(0, 1)
if flag: print('YES')
else: print('NO')
|
cs |
#BFS 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
import sys
from collections import deque
def BFS():
global myGraph, N
visited=[0]*(N)
deq = deque()
deq.append((0, 1))
while deq:
idx, num = deq.popleft()
if num == 1: num2 = -1
else: num2 = 1
for i in range(len(myGraph[idx])):
idx2 = myGraph[idx][i]
if visited[idx2] == 0:
visited[idx2]=num2
deq.append((idx2, num2))
if visited[idx2] != 0 and visited[idx2] == num:
return False
return True
if __name__ == "__main__":
input = sys.stdin.readline
N, M = map(int, input().split())
myGraph = [[] for _ in range(N)]
for _ in range(M):
a, b = map(int, input().split())
myGraph[a].append(b)
myGraph[b].append(a)
getFlag = BFS()
if getFlag:
print('YES')
else:
print('NO')
|
cs |