[백준] 13463 : Brexit (Python)

 

출처 : https://www.acmicpc.net/problem/13463

 

문제

오래전 은하계에서 아주 먼 옛날, 은하계 전역의 많은 국가로 구성된 대규모 성간 무역 연합이 있었습니다. 최근에 한 국가가 연합을 탈퇴하기로 결정했습니다. 그 결과, 다른 국가도 탈퇴를 고려하고 있는데, 주요 무역 파트너가 없어지면 연합에 참여하는 것이 더 이상 이롭지 않기 때문입니다.
당신은 국가 X의 우려하는 시민이며, 당신의 국가가 연합에 남을지 여부를 알고 싶어합니다. 당신은 서로의 무역 파트너인 모든 국가 쌍의 목록을 만들었습니다. 주어진 국가 Y의 무역 파트너의 절반 이상이 연합을 탈퇴하면, 국가 Y도 곧 뒤따를 것입니다. 이 정보를 바탕으로, 당신은 이제 당신의 본국이 연합을 탈퇴할지 여부를 결정하려고 합니다.

입력

입력은 네 개의 공백으로 구분된 정수 C, P, X, L이 포함된 한 줄로 시작합니다. 이는 국가의 총 수(2 ≤ C ≤ 200,000), 무역 파트너십 수(1 ≤ P ≤ 300,000), 본국의 수(1 ≤ X ≤ C)를 나타내며 마지막으로 가장 먼저 탈퇴하는 국가의 수를 나타냅니다. 이는 잠재적으로 재앙적인 결과를 초래할 수 있는 연쇄 반응을 일으킵니다(1 ≤ L ≤ C).
그 다음에는 P개의 줄이 이어지며, 각 줄에는 1 ≤ A₁ < B₁ ≤ C를 만족하는 두 개의 공백으로 구분된 정수 A; 및 B₁가 들어 있습니다. 이러한 줄은 국가 A; 및 B₁ 간의 무역 파트너십을 나타냅니다. 한 쌍의 국가가 두 번 이상 나열되지 않습니다.
처음에는 각 국가가 최소한 하나의 무역 상대국을 연합에 가입시켰습니다.

출력

각 테스트 케이스에 대해 "leave" 또는 "stay"가 포함된 줄을 하나씩 출력합니다. 이는 해당 국가가 연합을 탈퇴할지 아니면 잔류할지를 나타냅니다.

 

---

 

아이디어

요구사항 분석

'당신은 서로의 무역 파트너인 모든 국가 쌍의 목록을 만들었습니다.'

해당 요구사항은 다음과 같은 사항으로 그래프 문제임을 나타낸다.

• 노드 : 각 국가
• 간선 : 모든 국가 쌍(국가 X <-> 국가 Y, 양방향)

'주어진 국가 Y의 무역 파트너의 절반 이상이 연합을 탈퇴하면, 국가 Y도 곧 뒤따른다.'

국가 Y의 무역 파트너는 노드 Y와 연결된 다른 노드들을 지칭하는 것으로 해석 가능하다. 이를 바탕으로 다음과 같은 인사이트를 발견할 수 있다.

현재 국가 Y와 연결된 간선의 총 개수 >= 그래프 설정 시(초기)의 국가 Y와 연결된 간선의 개수 절반.(고정값)

 

알고리즘

요구사항 분석을 바탕으로 해당 문제에 대한 프로그램 설계를 어떻게 해야할까? 기존 유형과는 반대로 탐색해야 하는 특징을 가지고 있기 때문에 헷갈릴 수 있다. 차근차근 알아보자. 먼저 예제입력 4번의 케이스를 그래프로 시각화해보았다.

예제 입력 4번 그래프. (빨간색: 구하고자 하는 국가 X 노드, 파란색 : 첫 탈퇴 선언한 국가 L, 점선 : 탈퇴한 국가 L에 연결된 간선 삭제를 표현)

 

기존 유형과 다른 점을 위의 그래프를 예시로 들어 다음과 같이 정리해보았다.

• 기존
  • 간선을 한꺼번에 삭제한다.
  • 이후, 그래프 탐색을 진행한다.
• 현재
  • 탐색을 진행하면서, 간선을 한개씩 삭제한다.

 

탐색을 진행하면서, 간선을 한개씩 삭제하는 과정 그리고 자식 노드의 탈퇴 처리 과정을 살펴보자.

1. 10번 노드를 시작점으로 BFS 탐색 시작.
2. 6번 자식 노드 방문
   • 부모인 10번 노드와의 간선이 삭제되었으므로, 6번 자식 노드의 현재 간선의 개수는 1개.
   • 초기 설정의 간선 개수는 2개이다. (6-10, 6-5)
3. 현재 간선 개수 1개 >= 초기 설정 간선 개수의 절반(2 / 2 = 1) 이므로, 6번 자식 노드는 탈퇴 처리 갱신.
4. ...
5. 최종 목표인 1번 노드도 탈퇴할 것인가?

 

이 과정을 통해 다음과 같이, 탐색 프로세스를 설계할 수 있다.

• 탐색 시 사용될 해당 노드의 현재 간선의 개수를 저장하는 배열 필요. (delete_edges_counts : 1차원)
• 초기 해당 노드에 설정되었던 간선의 개수를 저장하는 배열 필요. (init_nodes_edges_counts : 1차원)
• 탐색을 진행하면서 탈퇴 여부를 기록하기 위한 배열 필요. 이는 방문처리를 함께한다. (leave_node_flags : 1차원)
• Queue의 원소는 탈퇴하는 노드(국가).
• 자식 노드들을 방문하면서, 간선을 하나씩 삭제하며 초기 간선 개수와 비교하는 연산 필요.

13463번 문제는 기존과 달리, 탐색 중에 간선을 하나씩 삭제하는 과정이 들어가기에 어렵게 느껴질 수 있다. 그렇지만, 요구사항 파악과 그래프 탐색 과정을 잘 생각해본다면 프로그램 프로세스를 잘 설계할 수 있는 문제였다.

 

정답 코드

# https://www.acmicpc.net/problem/13463
# Brexit
# 그래프 탐색, bfs

input=__import__('sys').stdin.readline
deque=__import__('collections').deque

def bfs(root):
    q=deque([root])
    leave_node_flags[root]=True
    
    while q:
        cur_node=q.popleft()
        # 탈퇴한 cur_node 국가의 파트너 국가들 탐색
        for next_node in graph[cur_node]:
            delete_edges_counts[next_node]+=1 # 해당 파트나 국가 간선 제거 가정.
            # 현재 Y의 간선개수 >= 초기 간선개수//2를 양변에 2를 곱한 수식으로 변형.
            # 나눌때 홀수인 경우, +1을 해야하기 때문에, 코드를 줄이기 위해서!
            # 초기 파트너 연합수(간선수) 절반 이상이고, 탈퇴하지 않았다면
            if delete_edges_counts[next_node]*2>=init_nodes_edges_counts[next_node] and not leave_node_flags[next_node]:
                leave_node_flags[next_node]=True # 해당 파트너 국가 탈퇴 처리
                q.append(next_node)

C,P,X,L=map(int,input().split())
graph=[[] for _ in range(C+1)]
delete_edges_counts=[0]*(C+1) # 탐색 시, 해당 노드의 제거되는 간선 개수
init_nodes_edges_counts=[0]*(C+1) # 초기 해당 노드에 연결된 간선 개수

for _ in range(P):
    start,end=map(int,input().split())
    graph[start].append(end)
    graph[end].append(start)

# init_nodes_edges_counts=[0]+[len(i) for i in graph]
for i in range(1,C+1):
    init_nodes_edges_counts[i]=len(graph[i])

leave_node_flags=[False]*(C+1) # 해당 노드가 연합 탈퇴를 했는지 여부
bfs(L) # 첫 탈퇴 국가를 시작으로 그래프 탐색 시작.

print(['stay','leave'][leave_node_flags[X]])