BOJ 백준 17837 새로운 게임 2 [JAVA]

문제  : https://www.acmicpc.net/problem/17837

[ 문제 요약 ]

• N*N 체스 판에서 K 개의 말을 놓고 게임을 합니다.
• 말은 1번부터 K 번까지 번호가 있고, 이동 방향은 상하좌우입니다. 하나의 말 위에 다른 말을 올릴 수 있습니다.
• 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 칠해져있습니다.
• 턴 한번은 1번 말부터 K 번 말까지 순서대로 이동 시키는 것이고, 말 이동시 위에 올려져 있는 말도 함께 이동합니다.
• 턴이 진행되던 중 말이 4개 이상 쌓이는 순간 게임이 종료됩니다.
• 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같습니다.
• [ 이동 칸이 흰 색인 경우 ] A 말을 이동시키는데 이동하는 칸이 흰 색인 경우 그 칸으로 이동합니다. 이동하려는 칸에 말이 이미 있는 경우에는 그 말들의 가장 위에 A 번 말을 올려놓습니다. 이때, A 번 말 위에 다른 말이 있는 경우 A 번 말과 그 위에 있는 모든 말이 이동합니다.
• [ 이동 칸이 빨간색인 경우 ] 빨간색인 경우 이동한 후 A 번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꿉니다. ex) A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B가 있었다면 최종 E, C, B, G, F, D, A
• [ 이동 칸이 파란색인 경우 ] A 번 말의 이동 방향을 반대로 하고 한 칸 이동합니다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있습니다.
• 체스판을 벗어나는 경우는 파란색과 같은 경우입니다.
• 게임이 종료되는 턴의 번호를 출력합니다. 턴 번호가 1000보다 크면 -1을 출력합니다.

[ 테스트 케이스 설명 ]

4 4 // 체스판 크기 (4<=12), 말 개수(4<=10)
0 0 2 0 // 체스판 정보(흰:0, 빨:1, 파:2)
0 0 1 0
0 0 1 2
0 2 0 0
2 1 1 // 말의 정보가 1번말부터 순서대로 주어짐
3 2 3 // 행, 열번호는 1부터시작, 이동 방향은 1부터순서대로→, ←, ↑, ↓를 의미
2 2 1
4 1 2
답 : -1

 

 

[ 알고리즘 분류 ]

• 구현
• 시뮬레이션

 

[ 문제 해설 ]

체스판의 각 구역마다 말의 순서를 관리해야 하므로 map을 큐로 선언하여 문제를 풉니다.

 

흰색일 때는 그냥 이동하며, 빨강일 때는 흰색과 똑같지만 이동만 뒤에서부터 역순으로 하면 됩니다. ArrayDeque를 쓰면 앞뿐만 아니라 뒤에서 부터도 데이터를 뽑아 올 수 있습니다.

 

그리고 이동하는 곳이 파란색이면 방향만 바꿔주고 흰 or 빨강 체크 로직을 태우면 간단히 문제를 풀 수 있습니다. 맵을 벗어나면 파랑과 같다고 했으니 패딩을 2로 넣어 외부는 파란색으로 만들어 주는 것이 범위 체크를 간단하게 하는 방법 중 하나입니다.

 

그리고 방향 전환 같은 경우, 1과 2가 쌍이고, 3과 4가 쌍입니다.

 

비트 연산으로 간단히 만들기 위해서는 -1을 해주어 0과 1이 쌍이고, 2와 3이 쌍이 되도록 만들면 XOR 연산으로 방향 전환을 할 수 있습니다.

 

now.dir = now.dir ^ 1;

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

class Main{
	
	static final int[][] dxy = {{0,1},{0,-1},{-1,0},{1,0}};
	static ArrayDeque<Node>[][] map;
	static int[][] color;
	static Node[] pos;
	static int N, M;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());// 체스판 크기 (4<=12)
		M = Integer.parseInt(st.nextToken());// 말 개수(4<=10)
		color = new int[N + 2][N + 2];
		pos = new Node[M];
		map = new ArrayDeque[N + 2][N + 2];
		
		for(int i=0; i<N + 2; i++)
			color[i][N + 1] = color[N + 1][i] = color[0][i] = color[i][0] = 2;
		
		for(int y=1; y<=N; y++)
		{
			st = new StringTokenizer(br.readLine());
			for(int x=1; x<=N; x++)
			{
				color[y][x] = Integer.parseInt(st.nextToken());// 체스판 정보(흰:0, 빨:1, 파:2)
				map[y][x] = new ArrayDeque<>();
			}
		}
		
		for(int order=0; order<M; order++)
		{
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());// 행, 열번호는 1부터시작
			int x = Integer.parseInt(st.nextToken());// 행, 열번호는 1부터시작
			int dir = Integer.parseInt(st.nextToken()) - 1;// 이동 방향은 1부터 순서대로→, ←, ↑, ↓를 의미
			pos[order] = new Node(order, y, x, dir);
			map[y][x].add(pos[order]);
		}
		
		for(int round = 1; round<=1000; round++)
		{
			for(Node now : pos)
			{
				int ny = now.y + dxy[now.dir][0];
				int nx = now.x + dxy[now.dir][1];
				
				if(color[ny][nx] == 2)
				{
					// 파랑인경우 방향을 반대로 바꾸고 ny, nx를 갱신
					now.dir = now.dir ^ 1;
					ny = now.y + dxy[now.dir][0];
					nx = now.x + dxy[now.dir][1];
				}
				
				if(color[ny][nx] == 0 || color[ny][nx] == 1)// 흰색 or 빨강인 경우
				{
					if(whiteAndRed(now, ny, nx, color[ny][nx] == 0))
					{
						System.out.print(round);
						return;
					}
				}
				
			}
		}
		
		System.out.print(-1);
	}

	static boolean whiteAndRed(Node now, int ny, int nx, boolean isWhite) {
		ArrayDeque<Node> dummy = new ArrayDeque<>();
		
		int y = now.y;
		int x = now.x;
		// 현재 큐에서 자기보다 앞에 있는 애들은 dummy로 뺀다.
		while(!map[y][x].isEmpty() && map[y][x].peekFirst().order != now.order)
			dummy.add(map[y][x].pollFirst());
		// 현 위치에서 남은걸 다음 스탭으로 옮긴다.
		while(!map[y][x].isEmpty())
		{
			Node node = isWhite ? map[y][x].pollFirst() : map[y][x].pollLast();
			node.y = ny;
			node.x = nx;
			map[ny][nx].add(node);
		}
		// dummy를 현재에 다시 넣는다.
		while(!dummy.isEmpty())
			map[y][x].add(dummy.pollFirst());
		
		return map[ny][nx].size() >= 4;
	}
	static class Node{
		int order, y, x, dir;
		Node(int order, int y, int x, int dir){
			this.order = order;
			this.y = y;
			this.x = x;
			this.dir = dir;
		}
	}
}

 

[ 테스트 케이스 ]

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

4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1
1 2 1
1 3 1
1 4 1
답 : 1

4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1
1 2 1
1 3 1
2 4 3
답 : 1

4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1
1 2 1
1 3 1
3 3 3
답 : 2

6 10
0 1 2 0 1 1
1 2 0 1 1 0
2 1 0 1 1 0
1 0 1 1 0 2
2 0 1 2 0 1
0 2 1 0 2 1
1 1 1
2 2 2
3 3 4
4 4 1
5 5 3
6 6 2
1 6 3
6 1 2
2 4 3
4 2 1
답 : 7

7 10
0 1 1 0 1 1 2
1 1 0 1 1 0 1
2 1 0 1 1 0 1
1 0 1 1 0 2 0
2 0 1 2 0 1 0
0 2 1 0 2 1 0
0 0 0 1 0 1 0
1 1 1
2 2 2
3 3 4
4 4 1
5 5 3
6 6 2
1 6 3
6 1 2
2 4 3
4 2 1
답 : 9