[BOJ/Java] 17837. 새로운 게임 2

[BOJ/Java] 17837. 새로운 게임 2

17837번: 새로운 게임 2

---

문제 해석

이 문제는 체스판에서 말을 이동시켜서 게임을 진행하는 시뮬레이션 문제다. 체스판의 각 칸은 흰색, 빨간색, 파란색으로 구분되어 있으며, 말은 특정 방향으로만 이동할 수 있다. 말은 다른 말 위에 올라탈 수 있으며, 이동 시 다양한 규칙에 따라 처리가 달라진다. 게임의 목표는 말이 네 개 이상 쌓이면 게임을 종료하는 것이다. 이 문제의 주요 도전은 말의 이동과 위치, 방향 변경 등을 정확히 처리하는 것이다.

풀이 과정

1. 체스판 초기화: map 배열에는 칸의 색 정보를, chessMap 배열에는 각 칸에 존재하는 체스 말의 목록을 저장한다.
2. 말의 이동: 말은 지정된 방향으로 이동을 시도하며, 이동 후의 칸이 파란색이거나 체스판을 벗어나면 반대 방향으로 다시 이동을 시도한다. 빨간색 칸에서는 말의 순서가 반전된다.
3. 게임 종료 조건: 어느 한 칸에 말이 네 개 이상 쌓이면 게임이 종료된다.
4. 턴 처리: 각 턴마다 모든 말을 순서대로 이동시키며, 1000턴을 초과하면 게임이 종료되지 않는 것으로 간주하고 -1을 출력한다.

코드

package edu.ssafy.im.BOJ.Gold.G2.No17837;

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

public class Main {
    private static int N, K;  // N: 체스판 크기, K: 말의 수
    private static int[][] map;  // 체스판 각 칸의 색 정보
    private static List<Integer>[][] chessMap;  // 각 칸에 위치한 말의 목록
    private static ArrayList<Chess> chessList;  // 말의 정보(위치, 방향)를 저장하는 리스트
    private static final int[][] direction = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};  // 동, 서, 북, 남 방향

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        chessMap = new ArrayList[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                chessMap[i][j] = new ArrayList<>();
            }
        }

        chessList = new ArrayList<>();
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            int d = Integer.parseInt(st.nextToken()) - 1;
            chessList.add(new Chess(x, y, d));
            chessMap[x][y].add(i);
        }

        sb.append(sol());
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static int sol() {
        for (int turn = 1; turn <= 1000; turn++) {
            for (int i = 0; i < chessList.size(); i++) {
                Chess c = chessList.get(i);
                int nx = c.x + direction[c.d][0];
                int ny = c.y + direction[c.d][1];

                if (go(i, c.x, c.y, nx, ny, false, c.d)) return turn;
            }
        }
        return -1;
    }

    private static boolean go(int chess, int x, int y, int nx, int ny, boolean status, int d) {
        if (nx < 0 || nx >= N || ny < 0 || ny >= N || map[nx][ny] == 2) {
            if (status) return false;
            if (d <= 1) d = d == 1 ? 0 : 1;
            else d = d == 2 ? 3 : 2;
            chessList.get(chess).d = d;

            nx = x + direction[d][0];
            ny = y + direction[d][1];

            return go(chess, x, y, nx, ny, true, d);
        } else {
            List<Integer> leavedChessList = new ArrayList<>(chessMap[x][y].subList(0, chessMap[x][y].indexOf(chess)));
            List<Integer> movedChessList = new ArrayList<>(chessMap[x][y].subList(chessMap[x][y].indexOf(chess), chessMap[x][y].size()));

            if (map[nx][ny] == 1) Collections.reverse(movedChessList);

            chessMap[nx][ny].addAll(movedChessList);
            if (chessMap[nx][ny].size() >= 4) return true;

            for (int idx : movedChessList) {
                chessList.get(idx).x = nx;
                chessList.get(idx).y = ny;
            }

            chessMap[x][y] = leavedChessList;
        }

        return false;
    }

    static class Chess {
        int x, y, d;

        public Chess(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
}

시간 복잡도 분석

이 문제의 시간 복잡도는 매 턴마다 모든 말을 이동시키므로 최대 𝐾×1000 번의 연산을 수행한다. 각 말의 이동은 𝑂(1)의 시간이 걸리므로 전체적인 시간 복잡도는 𝑂(𝐾)이다.

느낀점

이 문제를 통해 복잡한 시뮬레이션 문제에서의 조건 분기 처리와 상태 관리의 중요성을 다시 한 번 깨달았다. 체스판의 다양한 규칙과 말의 이동을 정확히 구현하는 과정에서 많은 디버깅이 필요했고, 그 과정이 매우 도전적이었다.