[Python] 32229번 B끼B끼 A끼A끼 수열 찾기

 

https://www.acmicpc.net/problem/32229

---

 

24/09/14

 

 

맷코컵 때 검수했던 문제 중 하나이다. 지문을 해석하는 재미가 있는 문제다. 그것과는 별개로, 제목이 별로다.

---

 

문제 접근 방식:

 

 

일단, 문제 해석을 하면 이 문제의 80%는 해결한 것과 다름이 없다.

 

 

먼저, 집합 $S$의 정의를 유의 깊게 보자. 문제에서 주어지는 입력은 $A, B, N$이다.

 

$S$는 순서쌍 $(x, y)$들의 모임인데, 작은 것이 $x$이고 큰 것이 $y$이다.($x < y$를 만족한다.)

 

또한, 이 둘의 차이는 $A$또는 $B$이며, $x$는 최소 $1$, $y$는 최대 $N$의 값을 가질 수 있다.

 

 

이제 수열 $P$의 정의를 유의 깊게 보자.

 

수열 $P$에는 $1$부터 $N$까지의 모든 수가 최소 하나씩 있고 $1$부터 $N$사이의 수들로만 구성되어 있다.

 

또한, 수열의 임의의 인접한 두 항을 순서쌍으로 만드는데, 작은 것이 왼쪽, 큰 것이 오른쪽으로 오도록 순서쌍을 만든다.

 

그러면 순서쌍들이 여러 개, 정확히는 수열 $P$의 길이보다 하나 적은 개수 만큼의 순서쌍들이 나올 것이다.

 

이 순서쌍들 $Q_i$는 다음과 같은 조건을 만족시켜야 한다.

 

1. $Q_i$는 모두 집합 $S$에 있어야 한다. 즉, $P$를 통해 만들어진 순서쌍은 $S$의 원소여야 한다.

 

2. $S$의 모든 순서쌍 $s$마다 $Q_i = s$가 되도록 하는 $i$가 존재한다. 쉽게 말하면, $S$에 있는 모든 순서쌍들은 수열 $P$를 통해서 등장한다.

 

3. 두 인덱스가 다르다면, $Q_i \neq Q_j$이다. 명제의 대우를 통해 바꿔서 말하면, $Q_i$와 $Q_j$가 같다면, 무조건 $i$와 $j$는 같은 인덱스라는 뜻이다. 이는 수열 $P$를 통해 만들어진 순서쌍은 중복이 없다는 말과 같은 말이다. (만약 중복이 있다면, $Q_i = Q_j$가 되는 경우고, 이는 3번 조건에 위배된다.)

 

 

즉, 1,2,3번 조건을 모두 고려하여 정리하면 다음과 같다.

 

수열 $P$를 통해 만들어지는 순서쌍들의 모임은 집합 $S$와 동일하고, 일대일 대응이 된다. 즉, 수열 $P$를 통해 만들어지는 순서쌍들의 모임은 집합 $S$와 정확히 동일하고 매칭된다.

 

 

이제 다음과 같은 관점을 하나 추가하면, 이 문제는 전형적인 문제로 바뀐다.

$1, 2, \dots, N$을 정점으로 간주하고, $(x, y)$를 간선으로 간주하자.

 

그래프적 관점으로 바라보면, 집합 $S$는 $1, 2, \dots, N$을 이어주는 간선들의 모임이 되고 수열 $P$는 이러한 간선들이 정확히 "한 번씩"만 쓰이도록 하는 경로라고 간주할 수 있다.

 

즉, 오일러 경로를 구성하는 문제로 변모하게 된다.

 

 

오일러 경로는 일반적으로 깊이 우선 탐색을 통해 구현되므로, 이를 생각하고 구현하면 된다.

 

유의할 점은, $A, B, N$이 따로 제한이 두어진 것이 아니고(즉, $N$보다 $A$나 $B$가 더 클 수 있다.), 수열 $P$에는 $1$부터 $N$까지 모든 정점이 들어가야 하므로(즉, 경로가 모든 정점을 잇도록 해야한다.) 이를 유의해서 구현해야 한다.

 

오일러 경로를 구하는 알고리즘을 통해 구하면, 간선 집합 $S$가 실제로는 모든 정점을 잇지 않음에도 불구하고 경로를 출력하는 경우도 있기 때문이다.

 

 

오일러 경로를 구하는 전형적인 알고리즘을 사용하지 않아도, 그래프의 모양이 특수하기 때문에 많은 조건 분기로도 해결할 수 있다. 하지만 이 풀이로는 내가 해결하지 않았고, 이 풀이가 그렇게 쉬운 것은 아니라고 생각되어 따로 적지는 않겠다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# subtask-2
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1_000_000)

path = []
def eulerpath(graph, edge, now, depth):
    for near in graph[now]:
        e = (min(now, near), max(now, near))
        if e in edge:
            edge.remove(e)
            eulerpath(graph, edge, near, depth+1)
    path.append(now+1)

def main():
    A, B, N = map(int, input().split())
    graph = [[] for _ in range(N)]
    edge = set()
    if A == B:
        for i in range(N):
            if i+A < N:
                graph[i].append(i+A)
                graph[i+A].append(i)
                edge.add((i, i+A))
    else:
        for i in range(N):
            if i+A < N:
                graph[i].append(i+A)
                graph[i+A].append(i)
                edge.add((i, i+A))
            if i+B < N:
                graph[i].append(i+B)
                graph[i+B].append(i)
                edge.add((i, i+B))
    odd_degree, now = 0, 0
    for i in range(N):
        degree = len(graph[i])
        if degree % 2:
            odd_degree += 1
            now = i
    if N == 1:
        print(1)
        print(1)
        return
    if (odd_degree == 0 or odd_degree == 2) and len(edge) > 0:
        eulerpath(graph, edge, now, 0)
        if len(edge) > 0:
            print(-1)
            return
        if len(set(path)) != N:
            print(-1)
            return
        print(len(path))
        print(*path)
        return
    else:
        print(-1)
        return
main()