백준17752 Messenger

작성일 | In

문제 링크

  • http://icpc.me/17752

문제 출처

  • 2012/2013 JOI Spring Camp Day4 1번

풀이

작년 여름에 풀지 못한 이후로 계속 출처를 찾아 헤매다 1년 만에 출처를 찾아서 풀었습니다. OI 문제라는 확신을 갖고 ojuz의 모든 인터랙티브/투스텝 문제를 뒤져보았지만 못 찾았었는데, 아직 ojuz에 안 올라왔더군요…

문제 요약

A와 B는 서로 다른 방에 있고, 복도에 4-by-4 크기의 체스판과 체스말 하나가 있습니다. A에게 어떤 자연수 X가 주어지면 복도에 있는 체스판과 체스말을 이용해서 B에게 X를 알려주어야 합니다.
진행 방식은 다음과 같습니다.

  1. A와 B가 각각 복도에 나올 순서를 나타내는 A, B로 구성된 문자열 S는 이미 정해져 있습니다.(grader에 입력으로 주어집니다.) 길이는 정확히 10 000이며, 같은 문자가 100번보다 많이 연달아 나오는 경우는 없습니다.
  2. InitA(T, X)와 InitB(T)가 호출됩니다. T는 테스트케이스 번호를, X(≤ 1 000 000 000)는 A가 B에게 전달해야 할 수를 의미합니다.
  3. 문자열 S에 따라 A 혹은 B가 복도로 나와 체스말을 인접한 칸으로 이동합니다.
    • A가 이동할 차례라면 GameA(I, J)가 호출되며, 이때 I, J는 현재 체스판의 위치(행, 열)를 의미합니다.
    • B가 이동할 차례라면 GameB(I, J)가 호출됩니다.
    • 체스판을 위/아래/왼쪽/오른쪽으로 이동할 경우 각각 -1/-2/-3/-4를 반환합니다.
    • GameB가 호출되는 시점에 정답을 알아냈다면 정답을 반환하면 됩니다.

풀이

한 번의 이동으로 얼마나 많은 정보를 전달할 수 있을까요? (1) A가 한 번 이동하고 B가 그것을 확인한 것과 (2) A가 100번 이동하고 B가 그것을 확인한 것이 모두 동일한 취급을 받는 것에 주의해야 합니다. 가장 먼저 생각해볼 수 있는 것은 비트 단위로 전송하는 것입니다. GameA와 GameB가 각각 최소한 90번 이상 호출되기 때문에 충분히 10억 이하(30비트 이하)의 정수를 전송할 수 있습니다.

잠시 TCP의 3 way-handshake를 생각해봅시다. 아래 과정을 통해 서버와 클라이언트 간의 동기화를 진행합니다.

  1. 클라이언트 : “나 보낸다!” (SYN)
  2. 서버 : “어 보내~” (SYN/ACK)
  3. 클라이언트 : “ㅇㅋ 시작한다” (ACK)

이 문제도 A와 B가 사전에 어떠한 규칙을 정해서, 정보 전송을 시작한다는 신호를 공유해야 합니다. 문제 풀이 로직의 흐름은 아래와 같이 표현할 수 있습니다.

  1. A와 B가 어떠한 규칙을 통해 동기화를 합니다.
  2. GameA가 호출된 경우 체스말을 적당히 옮겨서 한 비트를 전송합니다.
    • GameA가 연달아서 호출된 경우, 체스말을 적당히 옮겨서 아무 정보를 전달하지 않습니다.
  3. GameB가 호출된 경우 A가 전달한 정보를 수집하고, A가 정보를 전달하기 전 상태로 복구합니다.
    • GameB가 연달아서 호출된 경우, 체스말을 적당히 옮겨서 아무 정보를 수집하지 않고 정보를 전달하지도 않습니다.

(1) 동기화를 하는 규칙, (2) A가 정보를 전달하는 방법, (3) 어떤 함수가 연달아 호출되었을 때 아무 정보도 전달하지 않는 방법을 잘 정하면 문제를 해결할 수 있습니다. 그 중 한 가지 방법을 제시합니다.

동기화를 하는 규칙

2번 행에 체스말이 도달하는 것을 동기화의 시그널이라고 합시다.
GameA가 호출되는 시점에 이미 $I = 2$라면 이때부터 A는 정보 전송을 시작합니다.

A가 정보를 전송하는 방법

$I = 2$인 상황입니다.
만약 0을 전송해야 한다면 위로 이동하고, 1을 전송해야 한다면 아래로 이동합니다.

GameB가 호출되는 시점에 $I = 1$이라면 0을 전달받은 것이고, $I = 3$이라면 1을 전달받은 것입니다. 정보를 수집하고 다시 체스말을 2번 행으로 옮겨줍시다.

아무 정보도 전달하지 않는 방법

행 번호를 매개로 정보를 전달하기 때문에, 같은 행에서 움직이는 것은 정보 전달에 아무 영향도 미치지 않습니다. 왼쪽/오른쪽으로 이동하면 됩니다.

아래 코드는 구현의 편의를 위해 A와 B가 서로 동기화하지 않고, GameA가 호출되는 시점에 $I = 2$라면 일방적으로 정보를 전송합니다. 구체적인 방법은 코드(특히 MX, MX+1 부분)를 참고해주세요.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
using ll = long long;
constexpr int U = -1, D = -2, L = -3, R = -4, MX = 31;

namespace A{ ll ans; int bit; }

void InitA(int T, int X){
    A::ans = X | (1U << MX);
    A::bit = 0;
}

int GameA(int I, int J){
    if(I == 4) return U;
    if(I == 1 || I == 3) return J == 1 ? R : L;
    if(A::ans & (1LL << (A::bit++))) return D;
    return U;
}

namespace B{ ll ans; int bit; }

void InitB(int T){
    B::ans = B::bit = 0;
}

int GameB(int I, int J){
    if(I == 4) return U;
    if(I == 2) return J == 1 ? R : L;
    if(I == 1){ B::bit++; return D; }
    if(B::bit == MX) return B::ans;
    if(B::bit == MX+1) return B::ans >> 1;
    B::ans |= (1LL << (B::bit++));
    return U;
}