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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWQmA4uK8ygDFAXj&categoryId=AWQmA4uK8ygDFAXj&categoryType=CODE&problemTitle=%EC%98%A4%EC%85%80%EB%A1%9C&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

[SWEA] 4615. 재미있는 오셀로 게임 D3 - Simulation

 

문제

오셀로라는 게임은 흑돌과 백돌을 가진 사람이 번갈아가며 보드에 돌을 놓아서 최종적으로 보드에 자신의 돌이 많은 사람이 이기는 게임이다.
보드는 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를 출력한다.

 

---

소스코드

import java.io.*;
import java.util.StringTokenizer;

class Solution {
    static int arr[][];
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            arr = new int[n][n];

            arr[n / 2 - 1][n / 2 - 1] = 2;
            arr[n / 2][n / 2 - 1] = 1;
            arr[n / 2 - 1][n / 2] = 1;
            arr[n / 2][n / 2] = 2;

            for (int j = 0; j < m; j++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken()) - 1;
                int y = Integer.parseInt(st.nextToken()) - 1;
                int v = Integer.parseInt(st.nextToken());
                arr[y][x] = v;

                // 돌 먹기 (상,하,좌,우,대각)
                put(x, y, v);
            }

            int black = 0, white = 0;
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if(arr[j][k] == 1) black += 1;
                    else if(arr[j][k] == 2) white += 1;
                 }
            }

            sb.append("#" + (i + 1) + " " + black + " " + white + "\n");
        }

        System.out.println(sb);
    }

    // 상, 좌, 하, 우, 왼쪽 위 대각, 오른쪽 아래 대각, 왼쪽 아래 대각, 오른쪽 위 대각
    static int nx[] = {0, -1, 0, 1, -1, 1, -1, 1};
    static int ny[] = {-1, 0, 1, 0, -1, 1, 1, -1};
    static void put(int x, int y, int v) {
        arr[y][x] = v;
        for (int dir = 0; dir < 8; dir++) {
            check(x, y, dir);
        }
    }
    private static void check(int x, int y, int dir) {
        int rx = x + nx[dir];
        int ry = y + ny[dir];

        while (true) {
            if (!isRange(rx, ry) || arr[ry][rx] == 0)
                break;

            if (arr[y][x] != arr[ry][rx]) {
                rx += nx[dir];
                ry += ny[dir];
            } else
                break;
        }

        if (isRange(rx, ry) && arr[ry][rx] == arr[y][x]) {
            while (x != rx || y != ry) {
                arr[ry][rx] = arr[y][x];
                rx -= nx[dir];
                ry -= ny[dir];
            }
        }

    }

    private static boolean isRange(int x, int y) {
        if (0 <= x && x < n && 0 <= y && y < n)
            return true;
        return false;
    }
}

 

해결 방법

1. 입력된 칸을 기준으로 상, 하, 좌, 우, 대각선을 모두 탐색한다.
2. 이동이 된다면 오셀로 규칙에 맞게 이동한다.
3. 마지막 칸에서 다시 시작 칸으로 되돌아오며 돌의 색깔을 바꾼다.
4. 이를 반복한다.