cho.sh

오델로

유효한 6x6 오델로 게임의 수순이 주어질 때, 이를 재현해 최종 보드와 승자를 출력한다.

보통4시뮬레이션구현행렬완전 탐색면접 대비아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

오델로(Othello)는 검은색 또는 하얀색 원판을 6×66 \times 6 판 위에 늘어놓는 보드 게임이다. 일본에서는 オセロ, 국내에서는 오델로라고 부른다. 이름은 희곡 오셀로에서 따왔고, 오셀로의 이중성 또는 오셀로와 데스데모나가 이루는 흑백의 대비를 모티브로 삼았다고 한다. 지금도 일본을 비롯한 여러 나라에서 해마다 정기 대회가 열리며, 일본이 가장 활발하다. 주요 대회로 세계 오델로 챔피언십, 일본 명인전, 전일본 챔피언십, 왕좌전, 유럽 그랑프리가 있다. (출처: 나무위키)

위는 남규가 교양 수업 과제로 낸 리포트의 일부다. 리포트를 받은 교수님은 화가 나서 남규에게 오델로 대전을 신청했다. 남규는 오델로가 무엇인지 아직 몰라서 규칙을 인터넷에서 찾아보았다.

  • 처음에 판 가운데에 사각형으로 엇갈리게 배치한 돌 4개를 놓고 시작한다.

  • 돌은 반드시 상대방 돌을 양쪽에서 포위하여 뒤집을 수 있는 곳에 놓아야 한다.

  • 뒤집을 돌이 없으면 차례가 자동으로 상대방에게 넘어간다.

  • 아래 조건에 따라 양쪽 모두 더 이상 돌을 놓을 수 없게 되면 게임이 끝난다.

    • 돌 36개가 판에 가득 찬 경우 (가장 흔하다)
    • 어느 한쪽이 상대 돌을 모두 뒤집은 경우
    • 한 차례에 양쪽 모두 차례를 넘겨야 하는 경우

  • 게임이 끝났을 때 돌이 많은 플레이어가 승자가 된다. 돌의 개수가 같으면 무승부가 된다.

(출처: 위키백과)

그림으로 설명하면 아래와 같다.

위와 같은 상태의 게임판에서 시작해 검은 돌부터 차례를 이어 나간다. 파랗게 표시한 칸은 검은 돌을 놓을 수 있는 자리, 곧 하얀 돌을 최소 하나 검은 돌 두 개 사이에 넣을 수 있는 자리다. 빨갛게 표시한 칸은 검은 돌을 놓을 수 없는 자리의 예다.

검은 돌을 좌측 상단의 파란 칸 두 곳 중 하나에 놓으면 위에서 세 번째 행, 왼쪽에서 세 번째 열의 하얀 돌이 검은 돌에 포위되어 검은색으로 바뀐다. 우측 하단의 두 칸 중 하나에 놓으면 아래에서 세 번째 행, 오른쪽에서 세 번째 열의 하얀 돌이 검은색으로 바뀐다.

상대 돌을 포위하는 방향은 가로, 세로, 대각선 8방향 모두이며, 반드시 돌 하나만 감싸야 하는 것도 아니다. 예를 들면 아래와 같다.

검은 돌을 파란 자리에 놓으면 안에 O 표시가 있는 하얀 돌은 양 끝이 검은 돌로 막히므로 모두 검은색으로 바뀐다. X 표시가 있는 하얀 돌 두 개는 양 끝이 직접 막히지 않아 바뀌지 않는다.

이렇게 검은 돌부터 시작해 차례를 번갈아 가며 한 수씩 둔다. 그 밖의 세부 규칙은 위에 적은 규칙을 따른다.

남규는 규칙을 모두 공부한 뒤 교수님과 오델로 대전을 진행했고, 다행히 규칙에 맞는 플레이를 하기는 했다. 하지만 모두 패배해 F학점을 받을 위기에 처했고, 교수님은 며칠 뒤에 다시 한 번 기회를 주겠다고 선언했다.

남규는 우선 오늘의 플레이 기록을 복기하며 어느 부분이 문제였는지 알아보려 한다. 그런데 돌을 둔 위치만 기억할 뿐 게임판이 어떻게 생겼는지는 기억하지 못한다. 게임의 진행 과정에서 돌을 둔 위치가 모두 주어질 때, 게임판의 최종 상태와 승자를 구하자.

입력

첫 줄에 게임 로그의 수 NN이 주어진다. (1≤N≤321 \le N \le 32)

이어 NN개의 줄에 걸쳐 돌을 둔 위치 RR CC가 주어진다. RR행 CC열에 돌을 놓았다는 뜻이다. 행은 위부터 순서대로 1, 2, 3, ... 으로 번호를 매기고, 열은 왼쪽부터 순서대로 1, 2, 3, ... 으로 번호를 매긴다. 둘 중 한 명이 돌을 둘 수 없어 차례를 넘기는 경우가 생기는 게임은 입력으로 주어지지 않는다.

입력으로 주어지는 게임 로그는 항상 올바른 게임 로그다.

초기 게임판은 항상 (3, 3)과 (4, 4)에 하얀 돌 두 개, (3, 4)와 (4, 3)에 검은 돌 두 개가 놓인 상태이며, 검은 돌이 선을 잡는다.

출력

1행부터 6행까지: 한 행에 6글자씩, 6×66 \times 6 격자 형태로 게임판의 최종 상태를 출력한다. 빈 칸은 '.' (ASCII 46), 검은 돌은 'B' (ASCII 66), 하얀 돌은 'W' (ASCII 87)로 출력한다.

7행: 검은 돌을 잡은 플레이어가 승리했다면 Black을, 아니라면 White를 출력한다. 비기는 경우가 없는 입력만 주어진다.

힌트

정식 오델로는 8×88 \times 8 판에서 진행하지만, 설명의 편의를 위해 6×66 \times 6 판으로 바꾸었다.