[백준] 17837. 새로운 게임2

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

17837번: 새로운 게임 2

---

2019 하반기 삼성 공채 SW 역량테스트 시뮬레이션 문제 입니다. 제가 봤던 시험 시간에 나온 두 문제중 하나 였는데 게리멘더링2를 집중해서 풀다보니 문제만 읽고 시도를 못해보고 나왔었습니다ㅠㅠ. 이 문제의 특징은 2차원의 map 에서 각 공간에 데이터가 하나가 아니라 쌓이기 때문에 build라는 2차원 ArrayList 를 만들어서 해결했습니다. 색깔마다 움직일 때 순서가 바뀌기 때문에 저는 Deque를 사용했습니다.

그리고 주의해야 할 점은 배열을 벗어나거나 파랑색을 만나면 로직이 달라지는데, 반대방향으로 바꾼 후에 한칸을 더움직이고 그 자리가 또 배열 밖을 벗어나거나 파란색이 된다면 반대방향으로 움직여야 한다는 점이었습니다. 

[ 문제 풀이 ]

1. 2차원 int 배열 map 에는 각 영역의 색깔을 저장하고, 2차원 ArrayList 배열 build의 각 위치에는 말들을 저장합니다.

2. turn 의 횟수가 1000이 넘어가거나 말이 한개씩 움직였을 때 쌓인 말의 개수가 4개가 될 때 까지 while 문을 반복합니다.

3. K 개의 말을 처음 부터 한개씩 움직이기 시작하는데, 현재 말이 제일 밑에 있을 수도 있지만 쌓인 중간에 있을 수도 있기 때문에 idx 라는 변수를 통해서 말의 위치를 구합니다.

4. 현재 말부터 위에 쌓인 말들을 모두 queue에 저장합니다. queue 는 각 영역으로 움직일 때 순서가 바뀌기 때문에Deque 자료구조를 사용했습니다.

5. 다음 말이 움직이는 위치(nx, ny) 를 구하고 그 좌표의 색깔을 확인합니다.

6. 범위를 벗어나거나 파랑색 영역이면 이동방향을 바꾸고 한칸을 이동합니다.

7. 움직인 좌표가 범위를 벗어나거나 파랑색 영역이면 반대방향으로 움직입니다. 이 동작은 결국 원래자리로 가는 것입니다.

8. 흰색 영역이면 queue의 앞부터 poll 해서 쌓아줍니다.

9. 빨간색 영역이면 queue의 뒤부터 쌓아줘야 하기 때문에 pollLast 메소드를 사용합니다.

10. 옮겨진 말의 값을 갱신해줍니다.

---

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

public class Main {
	
	static class Horse {
		int x;
		int y;
		int d;
		Horse(int x, int y, int d){
			this.x=x;
			this.y=y;
			this.d=d;
		}
	}
	
	static int N, K, nx, ny, nd;
	static int[][] map, dir = {{0,0},{0,1},{0,-1},{-1,0},{1,0}};
	static Horse[] horses;
	static ArrayList<Integer>[][] build;
	static int[] change_dir = {0,2,1,4,3};
	static Deque<Integer> queue;
	
	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];
		build = new ArrayList[N][N];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				// 0:흰색, 1:빨간색, 2:파란색
				map[i][j] = Integer.parseInt(st.nextToken());
				build[i][j] = new ArrayList<>();
			}
		}
		
		horses = new Horse[K+1];
		
		for(int i=1; i<=K; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken())-1;
			int b = Integer.parseInt(st.nextToken())-1;
			// 1:동, 2:서, 3:북, 4:남
			int c = Integer.parseInt(st.nextToken());			
			horses[i] = new Horse(a, b, c);
			build[a][b].add(i);
		}
		
		int turn = 0;
		
		Out : while(true) {
			turn ++;
			// i번째 인덱스에 해당하는 말을 움직인다.
			for(int i=1; i<=K; i++) {
				Horse h = horses[i];
				int idx = -1;
				int size = build[h.x][h.y].size();
				
				// 현재 말 위치 구하기
				for(int j=0; j<size; j++) {
					if(build[h.x][h.y].get(j) == i) {
						idx = j;
						break;
					}
				}
				
				queue = new ArrayDeque();
				// 현재 말과 위에 쌓인말 저장해두기
				for(int j=idx; j<size; j++) {
					queue.offer(build[h.x][h.y].get(j));
				}
				// 지우기
				for (int j = idx; j < size; j++) {
					build[h.x][h.y].remove(idx);
				}
				
				// 말의 다음 움직일 위치
				nx = h.x+dir[h.d][0];
				ny = h.y+dir[h.d][1];
				nd = h.d;
				
				// 체스판을 벗어나거나 파랑색이면
				if(!isInside(nx, ny) || map[nx][ny] == 2) {
					// 파란색 영역이면
					// 이동 방향을 바꾸고
					nd = change_dir[h.d];
					// 한칸 이동
					nx += (dir[nd][0]*2);
					ny += (dir[nd][1]*2);
				}
				
				if(!isInside(nx, ny) || map[nx][ny] == 2) { // 배열 밖을 벗어났다면 그 자리 그대로
					nx -= dir[nd][0];
					ny -= dir[nd][1];
					while(!queue.isEmpty()) build[nx][ny].add(queue.poll());
				} else if(map[nx][ny] == 0) { // 흰색 영역이면 그대로 위에 쌓는다.
					while(!queue.isEmpty()) build[nx][ny].add(queue.poll());
				} else if(map[nx][ny] == 1) {// 빨간색 영역이면
					while(!queue.isEmpty()) build[nx][ny].add(queue.pollLast());
				} 
				
				if(build[nx][ny].size() >= 4 || turn > 1000) break Out;
				
				// 옮겨진 말의 값 갱신
				for(int j=0; j<build[nx][ny].size(); j++) {
					int hn = build[nx][ny].get(j);
					Horse oi = horses[hn];
					if(hn == i) horses[hn] = new Horse(nx, ny, nd);
					else horses[hn] = new Horse(nx, ny, oi.d);
					
				}
			}
		}
		if(turn > 1000) System.out.println(-1);
		else System.out.println(turn);
	}
	
	
	public static boolean isInside(int x, int y) {
		return x>=0 && x<N && y>=0 && y<N;
	}
}