[BOJ] 10037 Decorating the Pastures (문제풀이, PYTHON)

문제 링크

10037번: Decorating the Pastures

 

문제 설명

최대 50,000 개의 Node 와 최대 100,000 개의 Edge 가 존재한다. 그리고 이어진 노드들 중 이웃한 노드들은 서로 문자가 달라야 한다. (주어진 문자는 'F', 'J' 로 단 두 개)

그림으로 하면 다음과 같다.

이러한 Node 들의 유니온들이 있을 때 'J' 를 가장 많이 쓸 수 있을 때 그 수를 반환하는 것이다. 이웃한 노드끼린 서로 문자를 다르게 하면서 결국 다 따졌을 때 J의 수가 가장 많은 경우에 그 J 의 수를 반환하는 것.

예외 ) 해당 규칙을 지킬 수 없다면 -1 을 반환할 것

 

문제 해결

관심 가져야 할 부분

• 유니온으로 나눠 접근하기
• 각 유니온마다 J 를 가장 많이 가지게 할 때 그 경우의 수 구하기
• 해당 규칙을 지킬 수 없을 때 예외처리

유니온으로 나눠 접근하기

노드의 개수가 50,000 이므로 모든 노드를 순회하여 접근해도 부담되지 않는다. bfs 에서 방문기록을 담당하는 컴포넌트(visited 라 명명) 를 이용한다면 딱히 구현이 어려운 테크닉은 아니다. (저의 코드에선 visited 가 단순히 방문기록을 담당할 뿐만 아니라 최적의 경우 일 때 해당되는 문자 또한 담당합니다.)

이제 유니온 별로 접근이 가능하다.

 

각 유니온별 가질 수 있는 J 값 구하기

다행스럽게도 문자의 수가 'F', 'J' 로 단 두 개다. 처음엔 각 유니온의 In-Degree 가 0인 노드를 찾아 거기서부터 F, J 를 순서대로 가까운 노드부터 접근을 해볼까 생각을 하였는데 조금 생각을 정리하니 시작을 위한 노드라면 유니온에 해당되는 어느 노드라도 상관이 없다는 걸 알게 되었다.

시작 노드는 유니온의 어떤 노드라도 상관없다. 모든 노드를 순차적으로 접근할 것이니 시작 노드는 확보하였다.

그리고 그 유니온에서 얻을 수 있는 결과는 두 가지이다. 시작노드의 시작을 F 로 할 것인지, J 로 할 것인지에 따른 결과다.
따라서 visited 두 가지로 둬야 한다. 해당 유니온의 시작을 F 로만 할 때의 visited, J 로만 시작할 때의 visited.

이렇게 한 유니온을 두 번 bfs 하여 각 결과를 비교하고 J 의 수가 최대인 값을 축적해 나가면 된다.

 

해당 규칙을 지킬 수 없을 때 예외처리

해당 규칙을 지킬 수 없는 경우가 현재 노드로부터 이어진 다음 노드로 이동할 때 이미 그 F 나 J 로 값이 들어가 있는 경우이다. (특수한 순환하는 부분이 포함된 경우라 할 수 있다.)

이 부분은 다음 노드로 이동하기 전 이미 문자가 존재하는지와 존재한다면 현재 노드의 문자와 이미 존재하는 다음 노드의 문자가 동일한지에 따라 판단 내릴 수 있다.

시작노드를 F 로 혹은 J 로 한 경우 모두 해당 규칙을 지킬 수 없다면 -1 을 출력하고 종료한다.

(다행히 고려해야 할 예외의 경우가 단순한 것 같다.)

빨간 선이 규칙에서 어긋나는 부분

구현 코드

from collections import defaultdict, deque
from sys import stdin

n, m = map(int, stdin.readline().split())

edges = defaultdict(list)
visited_f = [-1 for _ in range(n+5)]
visited_j = [-1 for _ in range(n+5)]

for _ in range(m):
    i, j = map(int, stdin.readline().split())
    edges[i].append(j)
    edges[j].append(i)


def bfs(visited, node, letter):
    q = deque()
    q.append((node, letter))
    visited[node] = letter
    cnt_j = 1 if letter == 'J' else 0
    while q:
        cur_node, cur_letter = q.popleft()
        next_letter = 'F' if cur_letter == 'J' else 'J'
        for next_node in edges[cur_node]:
            if visited[next_node] != -1:
                if visited[next_node] == cur_letter:
                    return -1
                continue
            q.append((next_node, next_letter))
            visited[next_node] = next_letter
            if next_letter == 'J':
                cnt_j += 1
    return cnt_j


ans = 0
for i in range(1, n+1):
    if visited_f[i] != -1: # visited f 건 j 건 상관없다.
        continue

    visited_f[i] = 'F'
    cnt_j_1 = bfs(visited_f, i, 'F')
    visited_j[i] = 'J'
    cnt_j_2 = bfs(visited_j, i, 'J')

    if cnt_j_1 == -1 and cnt_j_2 == -1:
        print(-1)
        exit()
    elif cnt_j_1 > cnt_j_2:
        ans += cnt_j_1
    else:
        ans += cnt_j_2

print(ans)