[ 백준 / 17837번 ] Gold II - 새로운 게임 2 solved by 자바

 

www.acmicpc.net/problem/17837

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

 

[ 풀이 ] :

삼성다운 시뮬 문제 인데 나는 아주 그냥 쌓인 개수가 K개 이상인줄 알고 난리 쳤다.. 4개 이상이면 그냥 리턴..

 

[ 풀이 코드 ] : Deque를 이용하면 쉽게 풀 수 있다. 

 

package exer;

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

public class 새로운게임2 {	
	public static void main(String[] args) throws IOException {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st =new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int [][]arr =new int[N+2][N+2];
		for(int i =0; i<N+2; i++) {
			arr[i][0] = 2;
			arr[0][i] = 2;
			arr[N+1][i] = 2;
			arr[i][N+1] = 2;
		}
		Deque<Integer>[][]dq = new ArrayDeque[N+2][N+2];
		for(int i =1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j =1; j<=N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				dq[i][j]  =new ArrayDeque<Integer>();
			}
		}
		int[][]play = new int[K][3];
		for(int i =0; i< K ;i++) {
			st =new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			play[i][0] = x;
			play[i][1] = y;
			play[i][2] = Integer.parseInt(st.nextToken());//→, ←, ↑, ↓의
			dq[x][y].addLast(i);
		}
		int []di = new int[] {0,0,0,-1,1};
		int [] dj = new int[] {0,1,-1,0,0};
		int time = 1; 
		loop:
		while(time<1001) {
			for(int i =0; i< K ;i++) {
				int x= play[i][0];
				int y= play[i][1];
				if(arr[x+di[play[i][2]]][y+dj[play[i][2]]]==2) {
					play[i][2] = play[i][2]==1?2:play[i][2]==2?1:play[i][2]==3?4:3;
				}
				int d = play[i][2];
				int xx= x+di[d];
				int yy = y+dj[d];
				if(arr[xx][yy]==2) {
					continue;
				}
				switch(arr[xx][yy]) {
				case 0:
					int size = dq[x][y].size();
					boolean flag = false;
					for(int s = 0; s< size; s++) {
						int a = dq[x][y].pollFirst();
						if(a==i)flag = true;
						if(flag) {
							dq[xx][yy].addLast(a);
							play[a][0] = xx;
							play[a][1]= yy;
						}else {
							dq[x][y].addLast(a);
						}
					}
					break;
				case 1:
					while(!dq[x][y].isEmpty()) {
						int a = dq[x][y].pollLast();
						dq[xx][yy].addLast(a);
						play[a][0] = xx;
						play[a][1] =yy;
						if(a==i)break;
					}
				}
				if(dq[xx][yy].size()>3)break loop;
			}
			time++;
		}
		System.out.println(time==1001?-1:time);
		
	}

}

 

간단한 시뮬레이션 문제이기 때문에 크게 설명할 부분은 없고, 사이즈가 나가지 않기 위해

 

 

사이즈가 엄청큰 문제가 아니기 때문에 deque 2차원 배열을 선언해 주면서 초기화하였다, N+2의 크기로 만들어서

가장자리에 파란색을 넣어 처리가 편리하게 구현한다. ( 배열 밖으로 나갈 걱정을 안해도 된다. ) 

그리고 K개의 말을 받는다. (하.. 이렇게 쉬운거 나 왜 난리쳤지.. 후.. 4개.. 4개 이상이면..리턴...) 

그리고 이제 반복문을 돌면서 

시간에 따라서 값을 출력하게 한다. 

1000이하인 경우만 실행한다.

만약 가야할 값이 2라면, 방향을 바꿔준다. 

바꾸고 바라본 값도 2라면 그냥 넘기고 

아니라면 값을 이동시켜 준다. 

먼저 흰색 칸일 경우 , 

밑에서 부터 쌓아준다. queu를 돌면서 값을 넣어주는 것과 같이, 맨 아래서 부터 돌면서 

a와 같으면 그 이후의 값을 모두 다른 칸으로 옯겨준다. 

전의 값이라면 다시 넣어준다. 그래서 size만큼만 도는게 중요하다. 

이동할 칸이 빨간색이라면, deque를 스텍처럼 사용한다

뒤에서 부터 뽑으면서 다른 값에 넣어주고, 만약 넣어준 값이 지금 이동시킬 말이라면 끝내게 된다. 

 

그리고

제일 중요한 탈출 조건을 이용해 size가 4이상이 되면 나가게 된다. 

for(int i =0; i<K로  반복을 돌아도 나갈 ㅅ 없으면

시간을 더해준다. 

이제 time값을 출력해주면 끝