F. The Great Revegetation (Bronze)

- iknoom1107(최문기)

크기가 N인 배열 A에 다음 조건을 만족해야합니다.

• M개의 (i, j)쌍에 대해서, A[ i ] != A[ j ]

이때 출력되는 답은 배열 A를 정수로 표현했을 때 가장 작아야합니다.

저는 모든 i, j쌍에 대해서(i < j) A[ i ] != A[ j ]이면 A[ j ]++을 했는데 이러면 틀립니다.

<틀린 풀이>

N, M = map(int,input().split())
p = [1] * N
f = [] 
for _ in range(M):
	x, y = sorted(map(int,input().split()))
	f.append((x, y))

f.sort()

for x, y in f:
	if p[x-1] == p[y-1]: p[y-1] += 1

print(''.join(map(str,p)))

반례는 다음과 같습니다.

<입력>

4 3

1 2

2 4

3 4

<틀린 출력> 1212

<정답출력> 1213

반례를 보면 알겠지만 (2, 4)에서 조건을 체크해서 A[2] = 2, A[4] = 1이었는데

A[4]가 (3, 4)에서 증가해서 A[2] = A[4] = 2 가 되어버렸죠.

그래서 저 틀린 풀이에서 간단하게 (i, j)쌍만이 아니라 (j, i)쌍도 넣으면 정답풀이가 됩니다.

<정답 풀이>

N, M = map(int,input().split())
p = [1] * N
f = []
for _ in range(M):
	x,y = map(int,input().split())
	f.append((x-1,y-1))
	f.append((y-1,x-1))

for x, y in sorted(f):
	if p[x] == p[y]:
		if x < y: p[y] += 1
		else: p[x] += 1

print(''.join(map(str,p)))