BOJ 17837 새로운 게임 2(Java)
문제 탐색하기
- 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다.
- 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다.
- 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.
게임은 체스판 위에 말 K개를 놓고 시작한다.
- 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다.
- 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.
- 턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다.
- 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다.
- 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다.
- 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.
A번 말이 이동하려는 칸이 흰색인 경우에는
- 그 칸으로 이동한다.
- 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
- A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
빨간색인 경우에는
- 그 칸으로 이동한다.
- 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
- 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
파란색인 경우에는
- 이동 방향을 반대로 바꾸고 한 칸 이동한다.
- 이동하려는 칸이 파란색인 경우에는 이동하지 않는다.
체스판을 벗어나는 경우에는 파란색과 같은 경우이다.
입력
- 첫째 줄에 체스판의 크기 N, 말의 개수 K가 주어진다.
- 둘째 줄부터 N개의 줄에 체스판의 정보가 주어진다.
- 체스판의 정보는 정수로 이루어져 있고, 각 정수는 칸의 색을 의미한다.
- 0은 흰색, 1은 빨간색, 2는 파란색이다.
- 다음 K개의 줄에 말의 정보가 1번 말부터 순서대로 주어진다.
- 말의 정보는 세 개의 정수로 이루어져 있고, 순서대로 행, 열의 번호, 이동 방향이다.
- 행과 열의 번호는 1부터 시작하고, 이동 방향은 4보다 작거나 같은 자연수이고 1부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다.
- 같은 칸에 말이 두 개 이상 있는 경우는 입력으로 주어지지 않는다.
출력
- 게임이 종료되는 턴의 번호를 출력한다.
- 그 값이 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는
-1을 출력한다.
코드 설계하기
구현 방법
- 게임판과 말의 상태 관리
- N×N 크기의 2차원 배열로 게임판의 색상 정보 저장
- 각 칸마다
ArrayList를 사용하여 쌓여있는 말들의 정보 관리 Horse클래스로 각 말의 위치와 방향 정보 관리
- 턴 진행 방식
- 1번부터 K번 말까지 순서대로 이동
- 각 말이 이동할 때마다:
- 현재 말이 있는 위치에서 몇 번째 층에 있는지 확인
- 이동할 위치의 색상 확인
- 색상에 따른 이동 처리
- 이동 후 4개 이상 쌓였는지 확인
- 색상별 처리
- 흰색(0): 현재 말과 위의 말들을 그대로 이동
- 빨간색(1): 현재 말과 위의 말들을 역순으로 이동
- 파란색(2): 방향을 반대로 바꾸고 한 칸 이동
- 이동할 칸도 파란색이면 이동하지 않음
- 체스판 벗어남: 파란색과 동일하게 처리
시간 복잡도
- 입력:
O(N² + K)- 게임판과 말 정보 입력 - 턴 진행:
O(K)- 각 턴마다 K개의 말을 순서대로 이동 - 말 이동:
O(K)- 최악의 경우 한 칸에 K개의 말이 쌓여있을 수 있음 - 전체 시간 복잡도:
O(T×K²)- T는 턴의 수 (최대 1000)
- K는 말의 수 (최대 10)
정답 코드 (Java)
import java.io.*;
import java.util.*;
public class Main {
private static int N, K, cnt = 0;
private static ArrayList<Integer>[][] board;
private static Horse[] horses;
private static int[] dx = {0,0,-1,1};
private static int[] dy = {1,-1,0,0};
private static final int WHITE = 0;
private static final int RED = 1;
private static final int BLUE = 2;
private static final int MOD = 1_000;
static class Horse {
int x, y, dir;
Horse(int x, int y, int dir) {
this.x = x;
this.y = y;
this.dir = dir;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
board = new ArrayList[N][N];
horses = new Horse[K + 1];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = new ArrayList<>();
board[i][j].add(Integer.parseInt(st.nextToken()));
}
}
for (int i = 1; i <= K ; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken()) - 1;
int y = Integer.parseInt(st.nextToken()) - 1;
int dir = Integer.parseInt(st.nextToken()) - 1;
horses[i] = new Horse(x, y, dir);
board[x][y].add(i);
}
solution();
if (cnt >= MOD) {
System.out.println(-1);
} else {
System.out.println(cnt);
}
}
private static void solution() {
while (cnt < MOD) {
cnt++;
for (int i = 1; i <= K; i++) {
if (nextTurn(horses[i], i)) {
return;
}
}
}
}
private static boolean nextTurn(Horse h, int n) {
int cur_x = h.x;
int cur_y = h.y;
int level = 0;
int size = board[cur_x][cur_y].size();
for (int i = 1; i < size; i++) {
if (board[cur_x][cur_y].get(i) == n) {
level = i;
break;
}
}
int moved_x = cur_x + dx[h.dir];
int moved_y = cur_y + dy[h.dir];
int nextBlock = 2;
if(checkValid(moved_x,moved_y)) nextBlock = board[moved_x][moved_y].get(0);
if(nextBlock == 2)
{
switch (h.dir) {
case 0:
h.dir = 1;
break;
case 1:
h.dir = 0;
break;
case 2:
h.dir = 3;
break;
case 3:
h.dir = 2;
break;
}
moved_x = cur_x + dx[h.dir];
moved_y = cur_y + dy[h.dir];
if(!checkValid(moved_x,moved_y) || board[moved_x][moved_y].get(0) == 2) return false;
else
{
return move(board[moved_x][moved_y].get(0),level,size,cur_x,cur_y,moved_x,moved_y);
}
}
else
{
return move(nextBlock,level,size,cur_x,cur_y,moved_x,moved_y);
}
}
private static boolean move(int color, int start, int end, int x, int y, int mx, int my) {
List<Integer> moving = new ArrayList<>(board[x][y].subList(start, end));
if (board[mx][my].size() - 1 + moving.size() >= 4) return true;
if (color == RED) {
Collections.reverse(moving);
}
for (int num : moving) {
board[mx][my].add(num);
horses[num].x = mx;
horses[num].y = my;
}
while (board[x][y].size() > start) {
board[x][y].remove(board[x][y].size() - 1);
}
return checkGameOver(mx, my);
}
private static boolean checkValid(int x, int y) {
return x >= 0 && y >= 0 && x < N && y < N;
}
private static boolean checkGameOver(int x, int y) {
return board[x][y].size() - 1 >= 4;
}
}
Leave a comment