[PS] BOJ 15671 / 오델로
![[PS] BOJ 15671 / 오델로](/content/images/size/w2000/2025/09/-------------9.png)
문제 링크: https://www.acmicpc.net/problem/15671
구현 문제는 항상 재밌는 것 같습니다.
풀이
오델로?
6x6의 보드 판 위에서, 매 차례에 돌을 놓았을 때 상대의 돌을 자신의 돌로 감싸게 된다면, 자신의 돌로 감싼 상대의 돌을 모두 뒤집을 수 있는 게임입니다.
이렇게 서로의 차례를 반복하며, 보드판 전체를 자신의 돌로 만들거나, 더 이상 서로 뒤집을 수 있는 돌이 없을 때 게임이 종료됩니다.
구현하기
사실 규칙은 크게 중요하지 않습니다. 이 문제는 직접 돌을 놓아야 하는 문제가 아니고, 돌을 놓은 위치를 입력으로 받아 게임의 결과를 계산하기만 하면 되기 때문입니다.
따라서, 매 차례에 돌을 놓을 때 상대의 돌을 뒤집을 수 있다면 뒤집어주는 부분만 구현해주면 됩니다.
1) 초기 상태
# 타일 상수
EMPTY = 0
WHITE = 1
BLACK = 2
TILE_STR = [".", "W", "B"]
board = [[EMPTY for _ in range(7)] for _ in range(7)]
queue = deque()
board[3][3] = board[4][4] = WHITE
board[3][4] = board[4][3] = BLACK초기 상태 정의하기
보드판의 (3,3), (4,4) 에는 흰 돌이, (3,4), (4,3)에는 검은 돌이 미리 놓여있습니다.
타일 종류는 빈 칸을 0, 흰 돌을 1, 검은 돌을 2로 사용했는데, 코드의 가독성을 위해 각각을 상수 변수로 정의해 사용했습니다. 또, 이 상수값을 인덱스로 가지는 배열 TILE_STR에 대응하는 타일 문자열을 저장해 보드판을 출력하기에 용이하게끔 구현했습니다.
2) 상대 돌 뒤집기
DIRECTIONS = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))
def is_inside(r, c):
return 1 <= r <= 6 and 1 <= c <= 6
def check_board(r, c, stone):
for dr, dc in DIRECTIONS:
nr = r + dr
nc = c + dc
queue.clear()
while is_inside(nr, nc):
if board[nr][nc] == EMPTY:
break
elif board[nr][nc] == stone:
while queue:
nr, nc = queue.popleft()
board[nr][nc] = stone
break
else:
queue.append((nr, nc))
nr += dr
nc += dc
for i in range(1, int(input()) + 1):
r, c = map(int, input().split())
cur_turn = BLACK if i & 1 else WHITE
board[r][c] = cur_turn
check_board(r, c, cur_turn)상대의 돌을 뒤집는 코드
is_inside는 매개변수로 받은 좌표 (r, c)가 보드판 내부의 좌표인지를 판단하는 함수입니다.check_board는 현재 놓은 돌의 좌표 (r, c)와 놓은 돌의 종류stone을 매개변수로 받아 자신이 상대의 돌을 뒤집을 수 있는지 확인합니다.
오델로의 규칙에 따르면, 자신이 돌을 놓은 위치를 기준으로 8방향 (가로, 세로, 대각선)을 확인해 기존에 놓여있던 자신의 다른 돌과 지금 놓은 돌이 상대의 돌을 감싸고 있다면 뒤집을 수 있습니다.
check_board에서는 DIRECTIONS에 미리 정의해 둔 8개 방향의 좌표 변화량 (dr, dc)를 사용해 각 방향으로 보드를 탐색하며, 조건에 맞다면 상대의 돌을 뒤집습니다.
3) 보드판 및 결과 출력하기
def print_answer():
white = 0
black = 0
t = [""] * 6
for r in range(1, 7):
for c in range(1, 7):
if board[r][c] == WHITE:
white += 1
elif board[r][c] == BLACK:
black += 1
t[c - 1] = TILE_STR[board[r][c]]
print("".join(t))
if white > black:
print("White")
else: # 비기는 입력은 주어지지 않는다.
print("Black")결과 출력
전체 코드
from collections import deque
input = open(0).readline
# 타일 상수
EMPTY = 0
WHITE = 1
BLACK = 2
TILE_STR = [".", "W", "B"]
DIRECTIONS = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))
board = [[EMPTY for _ in range(7)] for _ in range(7)]
queue = deque()
board[3][3] = board[4][4] = WHITE
board[3][4] = board[4][3] = BLACK
def print_answer():
white = 0
black = 0
t = [""] * 6
for r in range(1, 7):
for c in range(1, 7):
if board[r][c] == WHITE:
white += 1
elif board[r][c] == BLACK:
black += 1
t[c - 1] = TILE_STR[board[r][c]]
print("".join(t))
if white > black:
print("White")
else: # 비기는 입력은 주어지지 않는다.
print("Black")
def is_inside(r, c):
return 1 <= r <= 6 and 1 <= c <= 6
def check_board(r, c, stone):
for dr, dc in DIRECTIONS:
nr = r + dr
nc = c + dc
queue.clear()
while is_inside(nr, nc):
if board[nr][nc] == EMPTY:
break
elif board[nr][nc] == stone:
while queue:
nr, nc = queue.popleft()
board[nr][nc] = stone
break
else:
queue.append((nr, nc))
nr += dr
nc += dc
for i in range(1, int(input()) + 1):
r, c = map(int, input().split())
cur_turn = BLACK if i & 1 else WHITE
board[r][c] = cur_turn
check_board(r, c, cur_turn)
print_answer()
solution.py