너무 피곤한 월요일. 간단한 이분 매칭 문제로 시작해보자.

BOJ 11180 - Paintball 링크
(2022.10.17 기준 P4)
(치팅하면 평생 월요일)

문제

N명이 페인트볼 게임을 하고 있고, 총알이 한 발씩 남아 있다. 서로 볼 수 있는 관계 M 쌍이 주어진다면, 모든 사람이 정확히 한 번씩 맞을 수 있는지 알아보고, 맞을 수 있다면 각자 맞춰야 하는 사람의 번호 출력

알고리즘

총알은 한 발씩 있고 모든 사람이 한 번씩 맞아야 하므로, 이분 매칭을 통하여 N개의 매칭이 되는지 확인해야 한다.

풀이

첫번째 예제를 살펴보자. 관계를 그림으로 나타내면
이렇게 나타낼 수 있는데, 모든 사람이 한 번씩 맞아야 하므로,
이렇게 되는 것이다.

두번째 예제를 살펴보면
이런 모양인데, 2번과 3번은 1번으로부터 맞을 수 있다. 그러므로, 둘 중 하나는 맞지 못하는 상태가 된다.
만약 1번이 2번을 쏜다면, 3번은 한번도 맞지 않게 되는 것이다. 그러므로 이 케이스는 Impossible을 출력해야 한다.

두번째 예제를 보면 알 수 있듯이, N명이 한 발씩 쏘아서 N명이 모두 맞으려면, 모두 한 발씩만 맞아야 가능하다.
결국, 이 문제는 이분 매칭이 성사된 결과의 수가 N개인지 파악하는 문제이며, N개가 성사가 되었다면, 매칭된 상대를 출력하면 되는 것이다.

코드

import sys; input = sys.stdin.readline

def match(i): # 이분 매칭
    for j in graph[i]: # 볼 수 있는 상대들
        if not visited[j]:
            visited[j] = True
            if connect[j] == -1 or match(connect[j]):
                connect[j] = i
                print(connect)
                return True
    return False

N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)] # 각자 볼 수 있는 상대들을 그래프로 나타내자.
for _ in range(M):
    A, B = map(int, input().split()) # 서로 볼 수 있으므로 양방향으로 이어준다.
    graph[A].append(B)
    graph[B].append(A)
connect = [-1] * (N + 1) # 맞힌 사람
result = 0 # 맞은 사람
for i in range(1, N + 1): # 1번 사람부터 이분 매칭 시작
    visited = [False] * (N + 1)
    if match(i): # 매칭이 성공했다면
        result += 1 # 한 명이 맞은 것이다.
# 맞은 사람이 N명이면 1번부터 맞힌 사람 출력. 아니면 Impossible 출력.
# 양방향이므로 맞힌 사람을 출력해도 AC
print(*connect[1:], sep = '\n') if result == N else print('Impossible')

여담

간단하고 기초적인 이분 매칭 문제였다. 다만, 독해력 그리고 양방향 간선으로 이루어진 그래프의 이해가 좀 필요한 문제였던 것 같다.