4615. 재미있는 오셀로 게임
문제 요약
오셀로라는 게임은 흑돌과 백돌을 가진 사람이 번갈아가며 보드에 돌을 놓아서
최종적으로 보드에 자신의 돌이 많은 사람이 이기는 게임이다.
보드는 4x4, 6x6, 8x8(가로, 세로 길이) 크기를 사용한다. 6x6 보드에서 게임을 할 때,
처음에 플레이어는 다음과 같이 돌을 놓고 시작한다(B : 흑돌, W : 백돌).
4x4, 8x8 보드에서도 동일하게 정가운데에 아래와 같이 배치하고 시작한다.
그리고 흑, 백이 번갈아가며 돌을 놓는다.
처음엔 흑부터 시작하는데 이 때 흑이 돌을 놓을 수 있는 곳은 백돌과 인접한 곳이다.
플레이어는 빈공간에 돌을 놓을 수 있다.
단, 자신이 놓을 돌과 자신의 돌 사이에 상대편의 돌이 있을 경우에만 그 곳에 돌을 놓을 수 있고,
그 때의 상대편의 돌은 자신의 돌로 만들 수 있다.
이런 식으로 번갈아가며 흑, 백 플레이어가 돌을 놓는다.
만약 돌을 놓을 곳이 없다면 상대편 플레이어가 다시 돌을 놓는다.
보드에 빈 곳이 없거나 양 플레이어 모두 돌을 놓을 곳이 없으면
게임이 끝나고 그 때 보드에 있는 돌의 개수가 많은 플레이어가 승리하게 된다.
문제 풀이
탐색해야 할 방향은 8가지가 있다.
각 방향대로 탐색하다가 종료해야 할 조건이 있다.
1. board판 넘어갈 경우
2. 아무돌이 없는 경우
3. 자신이 놓은 돌과 바로 다음 같은 돌이 있을 때가 된다.
탐색해야 할 조건은 자신이 놓은 돌과 다른 돌이 탐색될 경우이다. 그러다가 자신이 놓은 돌이 탐색되면 그 사이 돌은 자신이 놓은 돌의 색으로 변경하면 되는 것이다. 이것을 코드로 나타내면 다음과 같다.
def check(row, col, stone):
direction = [[1,1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1], [1, 0] ] ## 8방향
for direct in direction: ## 8방향 탐색
isdifferent = False ## 자신이 놓은 돌의 색과 다른 것이 탐색되었을 때 여부
new_row, new_col, tmp = row, col, [[row, col]] ## tmp는 탐색한 위치를 저장
while True:
new_row += direct[0]
new_col += direct[1]
## 탈출조건, 보드판 밖에 있을 경우, 아무돌도 없는 경우 종료
if new_row < 0 or new_row == n or new_col < 0 or new_col == n or board[new_row][new_col] == 0:
break
## 탈출조건, 자신이 둔 돌의 색이 바로 다음 탐색될 경우
if not isdifferent and stone == board[new_row][new_col]:
break
## 자신의 돌의 색과 다른 것이 탐색되면 isdifferent TRue로 변경, 해당 위치 저장
if stone != board[new_row][new_col]:
isdifferent = True
tmp.append([new_row, new_col])
## 자신이 놓은 돌이 탐색 되면 저장된 위치를 전부 자신이 놓은 돌로 변경
if isdifferent and stone == board[new_row][new_col]:
for t in tmp:
if stone == 1:
board[t[0]][t[1]] = 1
else:
board[t[0]][t[1]] = 2
break이제 주어진 위치를 check해주면서 해주면 된다.
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
arr = input().split(" ")
n, m = 0, 0
for i in range(len(arr)):
if i == 0:
n = int(arr[i])
elif i == 1:
m = int(arr[i])
board = [[0 for i in range(n)] for j in range(n)]
board[n // 2][n // 2], board[(n // 2) -1][(n // 2) - 1] = 2, 2
board[n // 2][(n // 2) - 1], board[(n // 2) - 1][n // 2] = 1, 1
case = []
def check(row, col, stone):
direction = [[1,1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1], [1, 0] ] ## 8방향
for direct in direction: ## 8방향 탐색
isdifferent = False ## 자신이 놓은 돌의 색과 다른 것이 탐색되었을 때 여부
new_row, new_col, tmp = row, col, [[row, col]] ## tmp는 탐색한 위치를 저장
while True:
new_row += direct[0]
new_col += direct[1]
## 탈출조건, 보드판 밖에 있을 경우, 아무돌도 없는 경우 종료
if new_row < 0 or new_row == n or new_col < 0 or new_col == n or board[new_row][new_col] == 0:
break
## 탈출조건, 자신이 둔 돌의 색이 바로 다음 탐색될 경우
if not isdifferent and stone == board[new_row][new_col]:
break
## 자신의 돌의 색과 다른 것이 탐색되면 isdifferent TRue로 변경, 해당 위치 저장
if stone != board[new_row][new_col]:
isdifferent = True
tmp.append([new_row, new_col])
## 자신이 놓은 돌이 탐색 되면 저장된 위치를 전부 자신이 놓은 돌로 변경
if isdifferent and stone == board[new_row][new_col]:
for t in tmp:
if stone == 1:
board[t[0]][t[1]] = 1
else:
board[t[0]][t[1]] = 2
break
for _ in range(m):
col, row, stone = map(int, input().split(" "))
check(row-1, col - 1, stone)
w_cnt, b_cnt = 0, 0
for i in range(n):
for j in range(n):
if board[i][j] == 2:
w_cnt += 1
elif board[i][j] == 1:
b_cnt +=1
print("#" + str(test_case) + " " + str(b_cnt) + " " + str(w_cnt))