시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB77031625939.785%

문제

오델로(Othello)는 검은색, 또는 하얀색 작은 원판을 6x6의 판 위에 늘어놓는 보드 게임이다. 보통 일본에서는 オセロ(오세로), 국내에서는 오델로라 부르고 있다. 어원은 오셀로 희곡으로 오셀로의 '이중성' 또는 오셀로와 데스데모나가 이루는 '흑백'의 대비를 모티브로 삼았다고 한다. 현재 독보적으로 활성화 되어있는 일본을 비롯하여 매년 여러 국가에서 정기 대회가 열리고 있으며 주요 대회로는 세계 오델로 챔피언십(이하 세계대회), 일본 명인전과 전일본 챔피언십, 왕좌전, 유럽 그랑프리 등이 있다. [출처 : 나무위키]

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

  • 처음에 판 가운데에 사각형으로 엇갈리게 배치된 돌 4개를 놓고 시작한다.
  • 돌은 반드시 상대방 돌을 양쪽에서 포위하여 뒤집을 수 있는 곳에 놓아야 한다.
  • 돌을 뒤집을 곳이 없는 경우에는 차례가 자동적으로 상대방에게 넘어가게 된다.
  • 아래와 같은 조건에 의해 양쪽 모두 더 이상 돌을 놓을 수 없게 되면 게임이 끝나게 된다.
    • 36개의 돌 모두가 판에 가득 찬 경우 (가장 일반적)
    • 어느 한 쪽이 돌을 모두 뒤집은 경우
    • 한 차례에 양 쪽 모두 서로 차례를 넘겨야 하는 경우
  • 게임이 끝났을 때 돌이 많이 있는 플레이어가 승자가 된다. 만일 돌의 개수가 같을 경우는 무승부가 된다.

[출처 : 위키백과]

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

위와 같은 상태의 게임판에서 시작하여, 검은 돌부터 차례를 이어나간다. 파랗게 표시한 부분은 검은 돌을 놓을 수 있는 영역(최소 하나의 하얀 돌을 검은 돌 두 개 사이에 넣을 수 있는 곳)이며, 빨갛게 표시한 부분은 검은 돌을 놓을 수 없는 영역의 예시이다.

만약 검은 돌이 좌측 상단의 두 파란 영역 중 하나에 돌을 놓는다면, 위에서 세 번째 줄, 왼쪽에서 세 번째 줄에 놓인 하얀 돌이 검은색 돌에 포위되므로 검은색으로 변하게 되며, 우측 하단의 두 영역 중 하나에 돌을 놓는다면 아래에서 세 번째, 오른쪽에서 세 번째에 놓인 하얀 돌이 검은색으로 변하게 된다.

이때, 상대 돌을 포위하는 것은 가로, 세로, 대각선 8방향 모두에서 이루어질 수 있으며, 반드시 하나의 돌만을 감싸야 하는 것은 아니다. 예시를 들면 아래와 같다.

만약 검은 돌이 파란 위치에 돌을 놓는다면, 내부에 O 표시가 있는 모든 하얀 돌은 양 끝이 검은 돌로 막혔으므로 검은색으로 변하게 된다. X 표시가 있는 두 하얀 돌은 양 끝이 직접 막히지 않았으므로 변하지 않는다.

이처럼 검은 돌부터 시작해 차례를 번갈아가며 한 수씩 두게 된다. 그 외의 세부 규칙은 상단에서 보았던 규칙(출처:위키백과)을 참고한다.

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

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

입력

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

이어 N줄에 걸쳐, 돌을 둔 위치 R C가 주어진다. 이는 돌을 R행 C열에 놓았다는 의미이다. 행은 위부터 순서대로 1, 2, 3, … 으로 번호를 매기며, 열은 왼쪽부터 순서대로 1, 2, 3, ... 으로 번호를 매긴다. 둘 중 한 명이 돌을 둘 수 없어 턴을 넘기는 경우가 생기는 게임은 입력으로 주어지지 않는다.

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

초기 게임판의 형태는 항상 (3,3), (4,4)에 백돌 두 개가, (3,4), (4,3)에 흑돌 두 개가 올려져 있는 상태이며, 흑돌이 선을 잡는다.

출력

1행 ~ 6행 : 행마다 6글자로, 6*6 격자 형태로 게임판의 최종 상태를 출력한다. 빈 칸은 ‘.’ (ASCII 46), 검은 돌은 ‘B’ (ASCII 66), 하얀 돌은 ‘W’ (ASCII 87) 로 출력한다.

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

예제 입력 1

6
3 2
4 2
5 3
2 2
2 1
3 5

예제 출력 1

......
BW....
.BWWW.
.WBW..
..B...
......
White

힌트

원래 정식 오델로는 8*8 보드판에서 진행하지만, 설명의 편의를 위해 6*6 보드판으로 변경하였다.