[백준] 15671. 오델로

문제 링크

[백준] 15671. 오델로

풀이 과정

final int SIZE = 6;
char[][] map = new char[SIZE + 1][SIZE + 1];
for (int i = 1; i <= SIZE; i++) Arrays.fill(map[i], '.');
map[3][3] = map[4][4] = WHITE;
map[3][4] = map[4][3] = BLACK;

먼저 6X6 크기의 2차원 배열을 만들고, 모든 요소를 . 으로 초기화한 뒤, 문제 조건에 맞게 백돌과 흑돌을 위치시킵니다.

for (int i = 0; i < N; i++) {
    set(horse, sc.nextInt(), sc.nextInt());
    horse = horse == BLACK ? WHITE : BLACK;
}

이후 로그 수 만큼, 해당 차례의 돌의 색깔과 함께 로그 정보(좌표)를 파라미터로 set 메소드 를 부릅니다. set 메소드 실행이 끝나면, 돌의 색깔을 바꿔, 차례를 맞춰줍니다.

static void set(char horse, int x, int y) {
    map[x][y] = horse;

    for (int d = 0; d < 8; d++) {
        int i = x, j = y;
        Stack<int[]> stack = new Stack<>();
        boolean stuck = false;

        while (true) {
            int ni = i + di[d], nj = j + dj[d];

            if (!inRange(ni, nj) || map[ni][nj] == '.') break;
            else if (map[ni][nj] == horse) {
                stuck = true;
                break;
            }

            stack.push(new int[]{ni, nj});
            i = ni;
            j = nj;
        }

        if (stuck) {
            while (!stack.isEmpty()) {
                int[] now = stack.pop();
                map[now[0]][now[1]] = horse;
            }
        }
    }
}

set 메소드 는 파라미터로 입력받는 좌표에, 입력받은 말을 위치시킵니다. 이후 8방향에 대해 아래와 같은 작업을 수행합니다.

• 해당 말의 색깔과 같은 색깔의 말이 나올때까지, 지나온 좌표들을 스택에 넣습니다.
• 만약, 다음 좌표가 보드판 범위를 벗어나거나, 아직 말이 놓이지 않은 위치라면, 더 이상 진행하지 않습니다.
• 만약, 다음 좌표에 위치하는 말이, 입력받은 말의 색과 같다면, 상대방 돌을 양쪽에서 포위하는 그림이므로, stuck 을 체크해두어, 그 사이의 말들을 뒤집어야겠다 라는 표시를 해둡니다.
• stuck 이 true 라면, 해당 진행 방향으로의 상대 말들은 포위되었으므로, 스택에 저장되어 있는 말들을 하나씩 꺼내어, 색깔을 바꿔줍니다.

코드

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    static int N;
    static char[][] map;
    static final int SIZE = 6;
    static int[] di = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dj = {0, 1, 1, 1, 0, -1, -1, -1};
    static final char BLACK = 'B', WHITE = 'W';

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new char[SIZE + 1][SIZE + 1];
        char horse = BLACK;

        for (int i = 1; i <= SIZE; i++) Arrays.fill(map[i], '.');
        map[3][3] = map[4][4] = WHITE;
        map[3][4] = map[4][3] = BLACK;

        for (int i = 0; i < N; i++) {
            set(horse, sc.nextInt(), sc.nextInt());
            horse = horse == BLACK ? WHITE : BLACK;
        }

        int blackCnt = 0, whiteCnt = 0;

        for (int i = 1; i <= SIZE; i++) {
            for (int j = 1; j <= SIZE; j++) {
                if (map[i][j] == BLACK) blackCnt++;
                else if (map[i][j] == WHITE) whiteCnt++;

                System.out.print(map[i][j]);
            }
            System.out.println();
        }

        System.out.println(blackCnt > whiteCnt ? "Black" : "White");
    }

    static void set(char horse, int x, int y) {
        map[x][y] = horse;

        for (int d = 0; d < 8; d++) {
            int i = x, j = y;
            Stack<int[]> stack = new Stack<>();
            boolean stuck = false;

            while (true) {
                int ni = i + di[d], nj = j + dj[d];

                if (!inRange(ni, nj) || map[ni][nj] == '.') break;
                else if (map[ni][nj] == horse) {
                    stuck = true;
                    break;
                }

                stack.push(new int[]{ni, nj});
                i = ni;
                j = nj;
            }

            if (stuck) {
                while (!stack.isEmpty()) {
                    int[] now = stack.pop();
                    map[now[0]][now[1]] = horse;
                }
            }
        }
    }

    static boolean inRange(int x, int y) {
        if (x < 1 || x > SIZE || y < 1 || y > SIZE) return false;
        return true;
    }
}