백준 1091번 카드섞기 문제 해설, 증명으로 확실하게 이해하자!
by injae Kim
백준 1091번 카드섞기 문제 해설
solved.ac 기준 골드 2 난이도의 문제입니다. 얼핏 보면 정말 단순한 시뮬레이션 구현 문제 이지만, 푸는 과정에서 함수의 일대일 대응 개념으로 풀이 방법을 확실하게 증명 할 수 있던 문제였습니다.
문제
지민이는 카지노의 딜러이고, 지금 3명의 플레이어(0, 1, 2)가 있다. 이 게임은 N개의 카드를 이용한다.
일단 지민이는 카드를 몇 번 섞은 다음에, 그것을 플레이어들에게 나누어 준다. 0번째 위치에 있던 카드가
플레이어 0에게 가고, 1번째 위치에 있던 카드는 플레이어 1에게 가고, 2번째 위치에 있던 카드는 플레이어
2에게 가고, 3번째 위치에 있던 카드는 플레이어 0에게 가고, 이런식으로 카드를 나누어 준다.
하지만, 지민이는 약간 사기를 치려고 한다.
지민이는 처음에 카드를 섞기 전에 카드의 순서를 알고 있고, 이 정보를 이용해 각 카드가
특정한 플레이어에게 보내지게 할 것이다.
카드를 한 번 섞을 때는 주어진 방법을 이용해서만 섞을 수 있고, 이 방법은 길이가 N인 수열 S로 주어진다.
카드를 한 번 섞고 나면 i번째 위치에 있던 카드는 S[i]번째 위치로 이동하게 된다.
각 카드가 어떤 플레이어에게 가야 하는지에 대한 정보는 길이가 N인 수열 P로 주어진다.
맨 처음 i번째 위치에 있던 카드를 최종적으로 플레이어 P[i] 에게 보내야한다.
지민이가 목적을 달성하기 위해 필요한 카드 섞는 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. N은 3보다 크거나 같고, 48보다 작거나 같은 3의 배수이다.
둘째 줄에 길이가 N인 수열 P가 주어진다. 수열 P에 있는 수는 0, 1, 2 중 하나이다.
셋째 줄에 길이가 N인 수열 S가 주어진다. 수열 S에 있는 수는 모두 N-1보다 작거나 같은 자연수
또는 0이고 중복되지 않는다.
출력
첫째 줄에 몇 번 섞어야 하는지 출력한다. 만약, 섞어도 섞어도 카드를 해당하는 플레이어에게
줄 수 없다면, -1을 출력한다.
예제입력
3
2 0 1
1 2 0
예제출력
2
문제 풀이
문제에서 주어진 입력이 카드 섞기전의 처음 카드 순서와 카드 섞는 방법 두가지 입니다.
우선 그림으로 카드가 어떻게 섞이게 되는지 보겠습니다!
문제에서 카드섞기전의 처음 카드 순서는 2 0 1 이며 카드 섞는 방법은 1 2 0 으로 주어졌습니다.
주어진 카드 섞는 방법 대로 카드를 1회 섞은 결과 입니다. 2 0 1 에서 1 2 0 로 카드가 섞였네요.
주어진 카드 섞는 방법대로 한번 더 섞어보겠습니다.
카드섞기의 종료 조건인, 0번째에 0번카드, 1번째에 1번카드, 2번째에 2번카드 … 를 충족시켰기 때문에 카드 섞기가 종료됩니다.
그림으로 보니까 뭔가 느낌이 오시나요?
우리에게 주어진 조건은 카드 섞기전의 처음 카드 순서와 카드 섞는 방법 이며 주어진 카드 섞는 방법대로 카드를 계속 섞다가, 종료 조건을 충족하면 그때 카드 섞기를 종료하고 몇 번 카드를 섞었는지 출력하면 될 것 같습니다!
하지만, 굉장히 쉬운 문제같아 보여도 무언가 걸리는점이 하나 있습니다.
만약 카드 섞는 방법이 위의 예제처럼 한칸씩 뒤로 미는것이 아닌, 뒤죽박죽 으로 섞는 방법이라고 하면 과연 카드를 언제까지 섞어야 할까요? 시간제한이 있는 문제인데 종료조건을 만족할 때 까지 무한대로 계속 섞어야할 까요? 애매합니다.
이 문제의 핵심 포인트는, 과연 언제 카드 섞기를 그만해도 되는가? 를 찾는 것 입니다.
문제 접근 방식
카드를 언제까지 섞다보면 그만 섞어도 문제의 종료조건을 충족하는지, 충족하지 않는지를 알 수 있을까요?
직감이 좋으신 분은 바로 생각이 날 수도 있겠지만, 저는 그런 사람이 아니기에, 하나하나 조건을 따져가며 증명해보겠습니다.
왼쪽은 카드를 섞어가는 과정을, 오른쪽은 각 단계에서 섞인 카드들의 상태를 의미합니다.
카드를 섞어가는 각 단계에서 카드들의 배열 상태를 A, B, … 로 정의해 보겠습니다.
어려운 말이 아니라 단지 카드가 이렇게 섞여있다 는 것을 나타내기 위해 A, B, … 로 정의한 것이므로 그냥 쉽게 이해해 주시면 됩니다!
카드를 섞어가는 과정에서, 같은 카드의 상태들이 반복되는 주기가 나타날 수도 있으며 이때 이 반복되는 주기를 “싸이클” 이라고 하겠습니다.
카드를 섞는 규칙은 문제에서 주어지므로, 카드를 섞어가는 과정에서 싸이클이 생길수도, 안생길 수도 있습니다.
따라서 제가 증명하고자 하는 바는 다음과 같습니다.
카드를 어떻게 섞던, 싸이클이 항상 존재하며, 그때 싸이클의 시작은 항상 카드를 섞기 전 처음 카드의 상태 이다.
위의 내용이 이 문제의 핵심 입니다.
- 카드를 어떻게 섞던지 항상 싸이클이 존재하며
- 이때 그 싸이클의 시작이 문제에서 주어진, 카드를 섞기 전 처음 카드의 상태 라면
우리는 카드를 섞다가 카드를 섞기 전 맨 처음 상태가 나오면, 카드섞기를 그만하고 종료조건을 충족하는지, 안하는지 판단한 후 카드 섞기를 종료하면 됩니다.
왜냐구요? 카드를 섞다가 맨 처음 카드 상태가 나왔다는 것 은, 그 뒤로도 맨 처음 카드 상태를 시작으로 하는 싸이클이 반복된다는 의미 이기 때문입니다! 같은 카드 배열 상태인 싸이클이 그대로 반복되는데 계속 카드를 섞어볼 필요는 없겠죠?
증명하고자 하는 바를 명확히 했으니, 우선 싸이클이 항상 존재하는가 ? 부터 증명해 보도록 하겠습니다.
싸이클은 항상 존재하는가?
싸이클은 존재 할 수도 있고, 안할수도 있습니다. 우선 싸이클이 존재하지 않는다고 가정해 보겠습니다.
그림 출처: https://j1w2k3.tistory.com/706
이때, 우리는 일대일 대응 이라는 개념을 짚고 넘어가야 합니다. 일대일 대응, 다들 한번씩 들어 보셨지 않나요? 위의 그림처럼 모든 원소가 각각 다른 원소로 대응될 때, 일대일 대응 이라고 할 수 있습니다. 중요한건 수학적인 내용이 아니고, 이 문제의 카드 섞는 방법 이 일대일 대응 을 만족한 다는 것 입니다.
모든 카드가 섞는 과정에 참여하며, 어떤 카드도 합쳐지거나 나눠지지 않고 단 하나의 위치로 이동합니다. 따라서, 카드 섞는 과정은 카드끼리의 일대일 대응 이라고 할 수 있습니다.
따라서 카드 상태 A 에서 카드를 섞었더니 카드 상태 B 가 되었고, 즉 A -> B 이고
또다른 카드 상태 C 에서 카드를 섞었더니 카드 상태 B 가 되었다면, 즉 C -> B 이면
카드 상태 A 는 카드 상태 C 와 같습니다!
카드 섞는 방식이 일대일 대응 관계 이기 때문에, 다른 카드 배열에서 같은 섞는 방식으로 카드를 섞었을때 같은 결과가 나올 수가 아예 없기 때문이죠.
카드를 섞을때 A -> B 이고 C -> B 이면 카드 상태 A == 카드 상태 C 이다.
위의 명제만 일대일 대응 개념을 이용하여 이해했다면, 사실 이문제의 모든 증명은 끝났습니다.
다시 싸이클로 가서 하나하나 따져보겠습니다.
싸이클이 존재하지 않을 때 는 위와 같습니다. 반복되는 카드 상태가 없이 섞을때마다 계속 다른 카드 상태가 나오게 됩니다.
과연 위와같이 싸이클이 존재하지 않을 수가 있을까요? 조금 다르게 접근 해 보겠습니다.
카드를 섞는 규칙이 모든 카드에 대해서 일대일 대응 관계이므로, 카드를 섞기전 맨 처음 상태에 첫번째 위치에 놓여있던 카드는 카드를 무한정 섞다보면 언젠가는 다시 첫번째 위치로 돌아올 수 밖에 없습니다.
이 때 첫번째 카드가 다시 첫번째 위치로 돌아오기까지 소요되는 카드 섞는 횟수를 X1 이라고 하겠습니다.
N 번째 카드가 다시 N 번째 위치로 돌아오기까지 소요되는 카드 섞는 횟수는 Xn 으로 하겠습니다.
그렇다면, X1 * X2 * … * Xn 번 만큼 카드를 섞으면, 모든 카드들이 맨 처음 카드를 섞기전 상태로 돌아오는 것 을 알 수 있죠!
따라서, 우리가 가정했던 싸이클이 존재하지 않는다 는 불가능 하다는 것 을 알 수 있습니다.
이제 남은건 싸이클이 존재할 때, 모든 싸이클의 시작이 카드를 섞기전 처음 상태 라는것 을 증명하는 것 입니다.
싸이클이 존재할 때, 모든 싸이클의 시작은 카드를 섞기 전 처음 상태 인가?
싸이클이 존재할 때는 싸이클의 길이가 싸이클이 아닌 부분의 길이보다 작거나, 같거나, 길거나 인 경우 밖에 존재하지 않습니다.
그러므로, 각각의 경우에 싸이클의 시작이 카드를 섞기 전 상태 임을 확인하면 우리의 가정이 참 이다 라고 증명할 수 있습니다. 하나하나 따져보겠습니다.
싸이클의 길이가 싸이클이 아닌 부분의 길이와 같을때 부터 살펴보겠습니다. 앞서 살펴본 일대일 대응 관계를 이용하면 싸이클의 시작이 맨 처음 상태인 A 임을 확인할 수 있습니다.
싸이클의 길이가 싸이클이 아닌 부분의 길이보다 작을때 입니다. 이 때도 싸이클의 시작이 맨 처음 상태인 A 임을 확인할 수 있습니다.
마지막으로 싸이클의 길이가 싸이클이 아닌 부분의 길이보다 길때 입니다. 이 때도 싸이클의 시작이 맨 처음 상태인 A 임을 확인할 수 있습니다.
정리하자면, 카드섞기를 언제까지 해야할 지 판단하기위해 우리가 세운 명제는 다음과 같습니다.
카드를 어떻게 섞던, 싸이클이 항상 존재하며, 그때 싸이클의 시작은 항상 카드를 섞기 전 처음 카드의 상태 이다.
이 명제를 증명하기위해
- 싸이클은 항상 존재한다
- 싸이클의 시작은 항상 카드를 섞기 전 처음 카드의 상태이다
를 우리는 하나하나 따져가며 증명 해냈습니다!
남은건 소스코드로 위의 과정을 옮기는 일 뿐 입니다.
소스코드
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
int idx[50];
int copy[50];
int init_state[50];
int suffle[50];
int num;
bool isSorted()
{
for (int i = 0; i < num; i++)
if (idx[i] != (i % 3))
return false;
return true;
}
void solve()
{
int count = 0;
while (isSorted() == false)
{
count++;
// 카드 섞기
for (int i = 0; i < num; i++)
::copy[i] = idx[i];
for (int i = 0; i < num; i++)
idx[suffle[i]] = ::copy[i];
// 카드가 섞기 전 맨 처음 상태인지 확인
for (int i = 0; i < num; i++)
{
if (init_state[i] != idx[i])
break;
if (i == num - 1)
{
// 싸이클이 발생, 아무리 섞어도 종료 조건을 충족하지 못함
cout << -1 << endl;
return;
}
}
}
cout << count << endl;
}
int main()
{
cin >> num;
for (int i = 0; i < num; i++)
{
cin >> idx[i];
init_state[i] = idx[i];
}
for (int i = 0; i < num; i++)
cin >> suffle[i];
solve();
return 0;
}
문제의 접근방식과 아이디어, 물을 제거하는 조건을 그대로 소스코드로 구현하였습니다.
문제풀이 후기
이 문제는 저도 종료조건을 직관적으로 생각하고 빠르게 구현하여 금방 맞출 수 있었던 문제입니다.
하지만, 내 직관이 진짜 맞을까? 가 궁금해서 하나하나 따져보고, 증명해보다보니 설명이 길어졌네요. 그에비해 코드는 매우 짧습니다!
증명 과정이 마치 고등학교 논술시험 문제를 푸는듯한 느낌이였습니다.
가끔은 직관에 의존하는 것 보다는 하나하나 조건을 나누고, 케이스별로 따져가는 것도 실력 향상에 도움이 되리라 생각합니다.
많은 도움이 되었길 바랍니다. 읽어주셔서 감사합니다.