백준 17837 : 새로운 게임 2

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

17837번: 새로운 게임 2

[ 문제풀이 ]

이번에도 시뮬레이션 문제이다. 2차원 List를 선언하여 말들을 관리해 주면 간단하게 해결할 수 있다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static int N, K;
	static int[][] map;
	static Node[] node;
	static List<Integer>[][] list;
	static int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
	static int[] direct = {1, 0, 3, 2};

	static class Node {
		int y, x, d;

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		map = new int[N][N];
		list = new ArrayList[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());
				list[i][j] = new ArrayList<>();
			}
		}

		node = new Node[K];
		for (int i = 0; i < K; ++i) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken()) - 1;
			int x = Integer.parseInt(st.nextToken()) - 1;
			int d = Integer.parseInt(st.nextToken()) - 1;

			node[i] = new Node(y, x, d);
			list[y][x].add(i);
		}

		bw.write(solve(1) + "\n");
		bw.flush();bw.close();br.close();

	}

	public static int solve(int turn) {
		if (turn > 1000) return -1;
		
		for (int i = 0; i < K; ++i) {
			if (moveTheNode(i) >= 4) {
				return turn;
			}
		}
		
		return solve(turn + 1);
	}
	
	public static int moveTheNode(int idx) {
		int y = node[idx].y;
		int x = node[idx].x;
		int d = node[idx].d;
		
		int ny = y + dir[d][0];
		int nx = x + dir[d][1];
		//이동할 벽이 파란 벽인 경우
		if (ny < 0 || nx < 0 || ny >= N || nx >= N || map[ny][nx] == 2) {
			node[idx].d = direct[d];
			ny = y + dir[node[idx].d][0];
			nx = x + dir[node[idx].d][1];
			//방향을 바꿔서 이동해도 파란 벽이면 종료
			if (ny < 0 || nx < 0 || ny >= N || nx >= N || map[ny][nx] == 2) {
				return list[y][x].size();
			}
		}
		
		int index = 0;
		int size = list[y][x].size();

		//현재 노드의 높이를 구함
		for (int i = 0; i < size; ++i) {
			if (list[y][x].get(i) == idx) {
				index = i;
				break;
			}
		}

		//이동할 벽이 빨간 벽이면 노드들의 순서를 변경
		if (map[ny][nx] == 1) {
			ArrayList<Integer> temp = new ArrayList<>();
			
			for (int i = index; i < size; ++i) {
				temp.add(list[y][x].get(i));
			}
			for (int i = 0; i < temp.size(); ++i) {
				list[y][x].remove(list[y][x].size() - 1);
			}
			for (int i = temp.size() - 1; i >= 0; --i) {
				list[y][x].add(temp.get(i));
			}
		}

		//노드들을 이동, 좌표도 변경해줌
		int cnt = 0;
		for (int i = index; i < list[y][x].size(); ++i) {
			int pos = list[y][x].get(i);
			node[pos].y = ny;
			node[pos].x = nx;
			list[ny][nx].add(pos);
			cnt++;
		}

		//이전의 노드 제거
		for (int i = 0; i < cnt; ++i) list[y][x].remove(list[y][x].size() - 1);

		return list[ny][nx].size();
	}
}