[SWEA][D3][#04615] 재미있는 오셀로 게임
작성:
업데이트:
카테고리: SWEA D3
태그: ProblemSolving, SWEA D3, SWEA PS
출처
학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.
문제
오셀로라는 게임은 흑돌과 백돌을 가진 사람이 번갈아가며 보드에 돌을 놓아서 최종적으로 보드에 자신의 돌이 많은 사람이 이기는 게임이다.
보드는 4x4, 6x6, 8x8(가로, 세로 길이) 크기를 사용한다. 6x6 보드에서 게임을 할 때, 처음에 플레이어는 다음과 같이 돌을 놓고 시작한다(B : 흑돌, W : 백돌).
4x4, 8x8 보드에서도 동일하게 정가운데에 아래와 같이 배치하고 시작한다.
그림 생략
그리고 흑, 백이 번갈아가며 돌을 놓는다.
처음엔 흑부터 시작하는데 이 때 흑이 돌을 놓을 수 있는 곳은 다음과 같이 4군데이다.
그림 생략
플레이어는 빈공간에 돌을 놓을 수 있다.
단, 자신이 놓을 돌과 자신의 돌 사이에 상대편의 돌이 있을 경우에만 그 곳에 돌을 놓을 수 있고, 그 때의 상대편의 돌은 자신의 돌로 만들 수 있다.
(여기에서 “사이”란 가로/세로/대각선을 의미한다.)
(2, 3) 위치에 흑돌을 놓은 후의 보드는 다음과 같다.
그림 생략
이런 식으로 번갈아가며 흑, 백 플레이어가 돌을 놓는다.
만약 돌을 놓을 곳이 없다면 상대편 플레이어가 다시 돌을 놓는다.
보드에 빈 곳이 없거나 양 플레이어 모두 돌을 놓을 곳이 없으면 게임이 끝나고 그 때 보드에 있는 돌의 개수가 많은 플레이어가 승리하게 된다.
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 보드의 한 변의 길이 N과 플레이어가 돌을 놓는 횟수 M이 주어진다. N은 4, 6, 8 중 하나이다.
그 다음 M줄에는 돌을 놓을 위치와 돌의 색이 주어진다.
돌의 색이 1이면 흑돌, 2이면 백돌이다.
만약 3 2 1이 입력된다면 (3, 2) 위치에 흑돌을 놓는 것을 의미한다.
돌을 놓을 수 없는 곳은 입력으로 주어지지 않는다.
출력
각 테스트 케이스마다 게임이 끝난 후 보드 위의 흑돌, 백돌의 개수를 출력한다.
흑돌이 30개, 백돌이 34인 경우 30 34를 출력한다.
예제
입력
1
4 12
1 2 1
1 1 2
4 3 1
4 4 2
2 1 1
4 2 2
3 4 1
1 3 2
2 4 1
1 4 2
4 1 2
3 1 2
출력
#1 0 16
My Sol
def dfs(i, j, c):
global mat
mat[i][j] = c
for di in (-1, 0, 1):
for dj in (-1, 0, 1):
# 이 방향에 내 돌이 있는지 체크
k = 1
ok = 0
while not ok:
si, sj = i+di*k, j+dj*k
if not (0<=si<N and 0<=sj<N): break
if not mat[si][sj]: break
if mat[si][sj]==c:
ok = 1
break
k += 1
# 이 라인에 내 돌이 없다면 다음 라인 확인
if not ok: continue
while k:
si, sj = i+di*k, j+dj*k
mat[si][sj] = c
k -= 1
T = int(input())
for tc in range(1, T+1):
N, M = map(int, input().split())
mat = [[0]*N for _ in range(N)]
k = N//2 - 1
mat[k][k] = mat[k+1][k+1] = 2
mat[k+1][k] = mat[k][k+1] = 1
for _ in range(M):
j, i, c = map(int, input().split())
j, i = j-1, i-1
dfs(i, j, c)
cnt1 = cnt2 = 0
for i in range(N):
for j in range(N):
if mat[i][j]==1:
cnt1 += 1
elif mat[i][j]==2:
cnt2 += 1
print(f'#{tc} {cnt1} {cnt2}')
구현 문제인데, 생각의 흐름만 잘 정리하면 그렇게 어렵지 않게 풀 수 있는 문제였다. 입력은 돌을 놓을 수 없는 곳에 놓지 않기 때문에 이 놓아진 돌이 적절한지에 대한 판단을 하지 않아도 된다. 입력을 처리해주고, 해당 들어온 입력의 행과 열을 구해준다. 여기부터 사방이 아닌 팔방으로 뻗쳐나가는데, 만약 범위를 넘지 않는 선에서 같은 색의 돌을 만나면, 이 사이의 돌은 같은 색으로 채워지게 하면 되겠다.
그래서 놓아진 돌의 좌표로부터 각 방향마다 계속 진행을 하며, 범위를 마칠 때까지 같은 색의 돌을 마주치지 못하거나 공백을 마주친다면, 해당 방향에서는 돌을 바꿀 수 없기 때문에 continue해서 다음 방향으로 조회할 수 있게 한다. 만약 이 조건을 통과한 방향이라면, 같은 색의 돌을 마주칠 때까지 이동한 횟수인 k만큼 같은 색으로 값을 지정해주면 되겠다.
의외의 복병을 만날 수 있었는데, 모든 칸이 돌이 채워지지 않더라도 게임이 끝날 수 있다는 사실이었다. 처음에는 이를 간과해서 완전 탐색으로 한 돌의 개수만 세고, 전체 칸에서 이 돌의 개수를 뺀 값을 다른 돌의 개수로 생각했는데, 그것이 아니라 빈 공간이 있더라도 두 돌이 모두 놓을 수 없는 상황이라면 게임이 끝나기 때문에 두 돌 모두 조회를 해주어야 했다.
결과
PASS
댓글남기기