[백준/자바] 17837 새로운 게임 2

사진 클릭시 문제로 이동

문제

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다.

새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K 개다. 말은 원판 모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.

게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.

턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.

• A번 말이 이동하려는 칸이
  • 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
    • A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
    • 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.
  • 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
    • A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
    • A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.
  • 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다.
  • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

다음은 크기가 4 ×4인 체스판 위에 말이 4개 있는 경우이다.

입력

첫째 줄에 체스판의 크기 N, 말의 개수 K가 주어진다. 둘째 줄부터 N개의 줄에 체스판의 정보가 주어진다. 체스판의 정보는 정수로 이루어져 있고, 각 정수는 칸의 색을 의미한다. 0은 흰색, 1은 빨간색, 2는 파란색이다.

다음 K개의 줄에 말의 정보가 1번 말부터 순서대로 주어진다. 말의 정보는 세 개의 정수로 이루어져 있고, 순서대로 행, 열의 번호, 이동 방향이다. 행과 열의 번호는 1부터 시작하고, 이동 방향은 4보다 작거나 같은 자연수이고 1부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다.

같은 칸에 말이 두 개 이상 있는 경우는 입력으로 주어지지 않는다.

출력

게임이 종료되는 턴의 번호를 출력한다. 그 값이 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력한다.

제한

• 4 ≤ N ≤ 12
• 4 ≤ K ≤ 10

예제 입력 1

4 4
0 0 2 0
0 0 1 0
0 0 1 2
0 2 0 0
2 1 1
3 2 3
2 2 1
4 1 2

예제 출력 1 

-1

:

---

설명

구현 문제다.

먼저 이동하려는 칸이 범위를 벗어나거나 파란 칸인 경우를 생각해보자.

그런 경우 방향을 반대로 하고 이동하려는 칸을 다시 확인해야 한다.

다시 이동하려는 칸이 범위를 벗어나거나 파란 칸인 경우 continue;

하얀 칸이거나 빨간 칸인 경우는 이동을 한다.

하얀 칸인 경우는 위로 그대로 쌓고

빨간 칸인 경우는 반대로 쌓는다.

 

이때 유의해야 할 점은 2 0 3 순서로 쌓여 있는 경우 0번째 말이 이동한다는 경우 0 3 만 이동하지 2까지 이동하지 않는다는 점이다! 자신과 자신 위의 쌓인 말만 이동하는 것!!

코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	public class BOJ17837 {
	static int n, k;
	static int map[][];
	static int dir[][] = {{0,1},{0,-1},{-1,0},{1,0}}; // →, ←, ↑, ↓
	static int loc[][];
	static String init[][];
	static int result = 0;
	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());
	map = new int[n][n];
	loc = new int[k][3];
	init = new String[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());
	init[i][j] = ".";
	}
	}
	for(int i = 0; i < k; i++) {
	st = new StringTokenizer(br.readLine());
	int r = Integer.parseInt(st.nextToken())-1;
	int c = Integer.parseInt(st.nextToken())-1;
	int d = Integer.parseInt(st.nextToken())-1;
	loc[i][0] = r;
	loc[i][1] = c;
	loc[i][2] = d;
	init[r][c] = Integer.toString(i)+" ";
	}
	while(++result <= 1000) {
	if(game()) break;
	}
	System.out.println(result > 1000? -1 : result);
	}
	static boolean game() {
	for(int i = 0; i < k; i++) {
	int tx = loc[i][0] + dir[loc[i][2]][0];
	int ty = loc[i][1] + dir[loc[i][2]][1];
	int D = 0;
	if(loc[i][2] == 0) {
	D = 1;
	}else if(loc[i][2] == 1) {
	D = 0;
	}else if(loc[i][2] == 2) {
	D = 3;
	}else {
	D = 2;
	}
	int ttx = loc[i][0] + dir[D][0];
	int tty = loc[i][1] + dir[D][1];
	if(!isRange(tx, ty)) {
	if(!isRange(ttx, tty)) {
	loc[i][2] = D;
	continue;
	}else if(isRange(ttx, tty) && map[ttx][tty] == 2) {
	loc[i][2] = D;
	continue;
	}
	tx = ttx;
	ty = tty;
	loc[i][2] = D;
	}else if(map[tx][ty] == 2) {
	if(!isRange(ttx, tty)) {
	loc[i][2] = D;
	continue;
	}else if(isRange(ttx, tty) && map[ttx][tty] == 2) {
	loc[i][2] = D;
	continue;
	}
	tx = ttx;
	ty = tty;
	loc[i][2] = D;
	}
	if(map[tx][ty] == 0) { // 흰색
	String ind[] = init[loc[i][0]][loc[i][1]].split(" ");
	int check = 0;
	if(0 < init[tx][ty].length() && init[tx][ty].charAt(0) == '.') init[tx][ty] = "";
	init[loc[i][0]][loc[i][1]] = "";
	for(int j = 0; j < ind.length; j++) {
	if(ind[j].equals(Integer.toString(i))) check = j;
	}
	for(int j = 0; j < check; j++) {
	init[loc[i][0]][loc[i][1]] += ind[j]+" ";
	}
	for(int j = check; j < ind.length; j++) {
	init[tx][ty] += ind[j]+" ";
	int index = Integer.parseInt(ind[j]);
	loc[index][0] = tx;
	loc[index][1] = ty;
	}
	if(init[tx][ty].length() == 0) init[tx][ty] = ".";
	String count[] = init[tx][ty].split(" ");
	if(count.length >= 4) {
	return true;
	}
	}else if(map[tx][ty] == 1) { // 빨간색
	String ind[] = init[loc[i][0]][loc[i][1]].split(" ");
	if(0 < init[tx][ty].length() && init[tx][ty].charAt(0) == '.') init[tx][ty] = "";
	init[loc[i][0]][loc[i][1]] = "";
	int check = 0;
	for(int j = 0; j < ind.length; j++) {
	if(ind[j].equals(Integer.toString(i))) {
	check = j;
	break;
	}
	else init[loc[i][0]][loc[i][1]] += ind[j]+" ";
	}
	for(int j = ind.length-1; check <= j; j--) {
	init[tx][ty] += ind[j]+" ";
	int index = Integer.parseInt(ind[j]);
	loc[index][0] = tx;
	loc[index][1] = ty;
	}
	if(init[tx][ty].length() == 0) init[tx][ty] = ".";
	String count[] = init[tx][ty].split(" ");
	if(count.length >= 4) {
	return true;
	}
	}
	}
	return false;
	}
	static boolean isRange(int x, int y) {
	return 0 <= x && x < n && 0 <= y && y < n;
	}
	}

view raw BOJ17837.java hosted with ❤ by GitHub