백준 17780 <새로운 게임>

내가 접한 시뮬레이션 중에 가장 어려운 축에 속하는 시뮬레이션 문제...

 

실제로 시험 칠 때도 마찬가지였지만 다시 봐도 헷갈리는 문제!

 

문제 풀이 순서

1. 1000번을 진행하면서 각각의 말이 아래 지점인지 확인!
2. 아래의 말일 경우에 파란색(범위가 벗어날 경우) , 빨간색, 흰색 경우를 고려해준다.
   1. 파란색일 경우 현재위치에서 방향을 바꿔 이동한다. --> 이 경우!! 이동 한 지점이 무조건 흰색이거나 파랑이 아니다!! 빨강일 경우도 있다!
   2. 빨강일 경우 순서를 뒤집어 준다!
   3. 흰색일 경우 모든말 그대로 움직인다.
3.  현재 위치의 말의 수가 4개 이상이면 return~

이 문제의 경우 시뮬레이션 문제를 많이 풀어봤었다면 생각할 수도 있는 문제였다.

 

각각의 말의 정보를 저장하기위한 miniun class를 따로 선언해줬다.

 

또한 s[][]라는 이차원 어레이 리스트를 이용해 각각의 말들을 쌓기 위해서 선언을 해줬다.!

이 점을 쉽게 생각하지 못할 것 이기 때문에 문제를 많이 풀어보는 필요성!

 

 

이 부분은 dir 방향을 내가 원하는 방식으로 설정하기위해서..ㅎ

 

다음 움직일 말이 어레이 리스트 0번에 저장되어 있지 않다면!! 가장 밑이 아니기 때문에 이동 불가!!

이 부분을 주의 깊게 보지 않으면 실수를 할 수도 ㅠ

 

 

  이 부분은 좌표를 이동해주고 파란색 or 칸을 벗어날 경우 방향을 반대로 바꿔주고 이동을 하는 것이다!

 

이경우에서 많은 실수가 있을 것이다! 

이 경우를 보면 2번 말이 위쪽 방향으로 이동하게 되고 다음칸이 파랑 이기 때문에 방향을 아래로 바꿔 이동하게 된다!!

 

중요한 점은!! 밟는 칸이 빨강이기 때문에 뒤집어 줘야 한다는 것이다!

다음 밟을 곳이 흰색 판일 경우 현재 순서 그대로 다음 칸에 넣어주기 때문에

거꾸로 모든 숫자를 스택에 저장해서 다시 꺼내는 방식으로 해결했다!!

 

여기서 ArrayList.remove()를  0부터 해주게 되면 다시 배열을 정리하는데 걸리는 시간이 있기 때문에 N^2승이 걸린다.  그러므로 스택에 넣었다가 큐에 넣었다.

 

다음 밟을 곳이 빨강 판일 경우 뒤집어서 넣어주기 때문에 끝에서 바로 다음 칸에 넣어주도록 했다.

 

코드를 더욱 단순화해주려면 파란색 칸을 밟거나 범위 벗어날 경우 다시 이동한 방향이 파란색칸 or 범위 벗어날 경우

가 아니면 i를 1 감소해주면 다시 그 말을 보기 때문에 더욱 짧아질 것이다. 

 

 

전체 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main{

	public static class miniun {
		int x;
		int y;
		int d;

		public miniun(int x, int y, int d) {
			this.x = x;
			this.y = y;
			this.d = d;
		}
	}

	static int map[][], dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }, result = -1, n, k;
	static ArrayList<Integer> s[][];
	static miniun num[];

	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 + 1][n + 1];
		num = new miniun[k];
		s = new ArrayList[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				s[i][j] = new ArrayList<Integer>();
			}
		}
		for (int i = 0; i < k; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			if (d == 1) {
				d = 1;
			} else if (d == 2) {
				d = 3;
			} else if (d == 3) {
				d = 0;
			} else if (d == 4) {
				d = 2;
			}
			num[i] = new miniun(x, y, d);
			s[x][y].add(i);
		}
		start();
		System.out.println(result);
	}
	private static void start() {
		// TODO Auto-generated method stub
		int time = 1;
		while (time <= 1000) {
			for (int i = 0; i < k; i++) {
				miniun next = num[i];
				int x=next.x;
				int y=next.y;
				if(s[next.x][next.y].get(0)!=i) {
					continue;
				}
				int x1 = next.x + dir[next.d][0];
				int y1 = next.y + dir[next.d][1];
				if (x1 < 1 || x1 > n || y1 < 1 || y1 > n || map[x1][y1] == 2) {
					next.d = (next.d + 2) % 4; // 방향 바꾸기
					x1 = next.x + dir[next.d][0];
					y1 = next.y + dir[next.d][1];
					if (x1 < 1 || x1 > n || y1 < 1 || y1 > n ||map[x1][y1] == 2) {
						next.d = (next.d + 2) % 4;
					}else if (map[x1][y1] == 0) {
						Stack<Integer> ne = new Stack<Integer>();
						while(s[next.x][next.y].size()!=0) {
							ne.add(s[next.x][next.y].remove(s[next.x][next.y].size()-1));
						}
						while(!ne.isEmpty()) {
							int nextnum=ne.pop();
							num[nextnum].x=x1;
							num[nextnum].y=y1;
							s[x1][y1].add(nextnum);
						}
						if (s[x1][y1].size() >= 4) {
							result = time;
							return;
						}
					} // 흰색판
					else {
						while (s[x][y].size()!=0) {
							int nextnum=s[next.x][next.y].remove(s[next.x][next.y].size() - 1);
							num[nextnum].x=x1;
							num[nextnum].y=y1;
							s[x1][y1].add(nextnum);
						}
						if (s[x1][y1].size() >= 4) {
							result = time;
							return;
						}
					}
				} // 파란색이나 반대 판
				else if (map[x1][y1] == 0) {
					Stack<Integer> ne = new Stack<Integer>();
					while(s[next.x][next.y].size()!=0) {
						ne.add(s[next.x][next.y].remove(s[next.x][next.y].size()-1));
					}
					while(!ne.isEmpty()) {
						int nextnum=ne.pop();
						num[nextnum].x=x1;
						num[nextnum].y=y1;
						s[x1][y1].add(nextnum);
					}
					if (s[x1][y1].size() >= 4) {
						result = time;
						return;
					}
				} // 흰색판
				else {
					while (s[x][y].size()!=0) {
						int nextnum=s[next.x][next.y].remove(s[next.x][next.y].size() - 1);
						num[nextnum].x=x1;
						num[nextnum].y=y1;
						s[x1][y1].add(nextnum);
					}
					if (s[x1][y1].size() >= 4) {
						result = time;
						return;
					}
				}
			}
			time++;
		}

	}

}