[SWEA] 4615_재미있는 오셀로 게임

📕 문제

오셀로라는 게임은 흑돌과 백돌을 가진 사람이 번갈아가며 보드에 돌을 놓아서 최종적으로 보드에 자신의 돌이 많은 사람이 이기는 게임이다.
보드는 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. 우선 N*N의 2차행렬을 만들어주고 가운데를 초기값으로 채운다.

2. M줄에 걸쳐 입력되는 돌의 위치와 색이 담겨있는 리스트를 Go라는 리스트에 담는다.

3. 이번엔 가로 세로 대각선을 다 봐줘야하기 때문에 4방이 아닌 8방으로 방향 리스트를 만들어준다.

4. Go리스트에서 앞에서 하나씩 빼면서 팔방을 봐주고 다음 칸이 지금 색과 다르고 0이 아니고 벽이 아니면 그 칸의 좌표를 change라는 리스트에 담는다.

5. change라는 리스트를 만들어준 이유는 검 흰 흰 (새로 둔)검 일 경우 흰 돌 두개가 다 바뀌어야하기 때문에 좌표들을 다 담아서 그 좌표의 칸들의 색을 다 바꿔주기 위해서이다.

6. 만약 change에 마지막으로 들어간 좌표가 벽이아니고 0이 아니고 change의 길이가 1 이상이라면 change안의 좌표들에 해당되는 칸의 돌들의 색을 다 바꿔준다,

( 이렇게 조건을 준 이유는 다음과 같다.)

• 검 흰 흰 벽(즉 인덱스 넘어섬) -> 이때는 바꿔주면 안되기 때문
• 검 흰 흰 0 -> 이때도 바꿔주면 안됨
• change는 처음에 무조건 옆에 있는 좌표가 들어가면서 초기화가 되기 때문에 1 이상이어야 바꿀 돌이 있다는 뜻임

7. 마지막으로 2차 행렬을 모두 돌면서 흰색과 검은색의 개수를 세주면 끝!

 

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    matrix = [[0 for _ in range(N)] for _ in range(N)]
    matrix[N//2-1][N//2-1:N//2+1] = [2, 1]
    matrix[N//2][N//2-1:N//2+1] = [1, 2]
    Go = []
    for _ in range(M):
        Go += [list(map(int, input().split()))]

    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    while Go:
        x, y, c = Go.pop(0)
        matrix[y-1][x-1] = c

        for dy, dx in dxy:
            ny, nx = y - 1 + dy, x - 1 + dx
            change = [[ny, nx]]

            while -1 < nx < N and -1 < ny < N and matrix[ny][nx] != 0 and c != matrix[ny][nx]:
                ny, nx = ny + dy, nx + dx
                change.append([ny, nx])

            if len(change) > 1 and -1 < nx < N and -1 < ny < N and matrix[ny][nx] != 0:
                for i, j in change:
                    matrix[i][j] = c

    b_cnt = 0
    w_cnt = 0
    for i in range(N):
        for j in range(N):
            if matrix[i][j] == 1:
                b_cnt += 1
            elif matrix[i][j] == 2:
                w_cnt += 1
    print('#{} {} {}'.format(tc, b_cnt, w_cnt))