[BAEK] 17780. 새로운 게임

11월 13일 in Category / ProblemSolving

[BaekJoon] 17780번 새로운 게임
삼성 기출문제

17780. 새로운 게임

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

public class Main {
	
	static int N,K;
	static int[][] map; // 0 흰, 1빨, 2파
	static int[][] moveMap;
	static Horse[] horseInfo;
	static int[][] dir = { {0,0},{0,1},{0,-1},{-1,0},{1,0} }; // 우,좌,상,하
	static boolean fourHorse;
	static int turn;
	static int result;

	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());
		K = Integer.parseInt(st.nextToken());
		map = new int[N+1][N+1];
		moveMap = new int[N+1][N+1];
		horseInfo = new Horse[K+1]; //행,열,이동방향
		result = -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());
			}
		}
		
		for(int i=1;i<=K;i++) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			int direction = Integer.parseInt(st.nextToken());
			ArrayList<Horse>list = new ArrayList<>();
			horseInfo[i] = new Horse(i, y, x, direction, list);
			moveMap[y][x] = i;
		}
		
		while(turn<=1000 && !fourHorse) {
			turn++;
			move();
		}
		
		result = turn<=1000 ? turn : -1;
		
		System.out.println(result);
	}
	
	public static void move() {
		for(int i=1;i<=K;i++) {
			Horse horse = horseInfo[i];
			int listSize = horse.list.size();
			
			// 가장 아래에 있는 말이면 이동한다.
			if( moveMap[horse.y][horse.x] == horse.number) {
				int dr = horse.y + dir[horse.direction][0];
				int dc = horse.x + dir[horse.direction][1];
				// 범위 안
				if(dr>0 && dc>0 && dr<=N && dc<=N) {
					switch(map[dr][dc]) {
					// 흰 => 이동하는 칸에 말 있으면 위에 올림
					case 0:
						if(moveMap[dr][dc]!=0) { // 이동하는 자리에 다른 말이 있는 경우
							Horse origin = horseInfo[moveMap[dr][dc]];
							moveMap[horse.y][horse.x] = 0;
							
							horse.y = dr;
							horse.x = dc;
							
							ArrayList<Horse> newList = new ArrayList<Horse>();
							
							for(int j=0;j<listSize;j++) {
								Horse nextHorse = horse.list.get(j);
								nextHorse.y = dr;
								nextHorse.x = dc;
								newList.add(nextHorse);
							}
							
							horse.list.clear();
							origin.list.add(horse);
							origin.list.addAll(newList);
							
							listSize = origin.list.size();
							
						}else { // 이동하는 자리에 다른 말이 없는 경우
							moveMap[horse.y][horse.x] = 0;
							horse.y = dr;
							horse.x = dc;
							
							for(int j=0;j<listSize;j++) {
								Horse nextHorse = horse.list.get(j);
								nextHorse.y = dr;
								nextHorse.x = dc;
							}
							
							moveMap[dr][dc] = horse.number;
						}
						break;
					// 빨 => 순서 뒤집어서 올림
					case 1:
						if(moveMap[dr][dc]!=0) {// 이동하는 자리에 다른 말이 있는 경우
							Horse origin = horseInfo[moveMap[dr][dc]];
							moveMap[horse.y][horse.x] = 0;
							horse.y = dr;
							horse.x = dc;
							
							for(int j=listSize-1;j>=0;j--) {
								Horse nextHorse = horse.list.get(j);
								nextHorse.y = dr;
								nextHorse.x = dc;
								origin.list.add(nextHorse);
							}
							
							horse.list.clear();
							origin.list.add(horse);
			
							listSize = origin.list.size();
						}else {// 이동하는 자리에 다른 말이 없는 경우
							moveMap[horse.y][horse.x] = 0;
							horse.y = dr;
							horse.x = dc;
							
							if(listSize==0) {
								moveMap[dr][dc] = horse.number;
								break;
							}

							Horse firstHorse = horse.list.get(listSize-1);
							firstHorse.y = dr;
							firstHorse.x = dc;
							
							for(int j=listSize-2;j>=0;j--) {
								Horse nextHorse = horse.list.get(j);
								nextHorse.y = dr;
								nextHorse.x = dc;
								firstHorse.list.add(nextHorse);
							}
							horse.list.clear();
							firstHorse.list.add(horse);
							moveMap[dr][dc] = firstHorse.number;
							
						}
						break;
					// 파 => 방향 반대로 변경 후 한 칸이동
					case 2: // 또 파랑색이면 이동없이 방향 변경만
						if(changeDirection(horse)) {
							i-=1;
							continue;
						}
					}
					
				}else { // 범위 넘어가면 파란색과 동일
					if(changeDirection(horse)) {
						i-=1;
						continue;
					}
				}
			}
			
			if(listSize>2) {
				fourHorse=true;
				return;
			}
		}
	}
	public static boolean changeDirection(Horse horse) {
		switch(horse.direction) {
		case 1:
			horse.direction = 2;
			break;
		case 2:
			horse.direction = 1;
			break;
		case 3:
			horse.direction = 4;
			break;
		case 4:
			horse.direction = 3;
			break;
		}
		
		int dr = horse.y + dir[horse.direction][0];
		int dc = horse.x + dir[horse.direction][1];
		
		// 이동방향 변경했음에도 또 파랑인지 판별
		if(dr>0 && dc>0 && dr<=N && dc<=N && map[dr][dc]!=2)
			return true;
		else
			return false;
	}
}

class Horse{
	public int number;
	public int y;
	public int x;
	public int direction;
	public ArrayList<Horse> list; // 자기자신 외에 위로 올라가는 말들
	
	public Horse(int number,int y,int x,int direction,ArrayList<Horse> list) {
		this.number = number;
		this.y = y;
		this.x = x;
		this.direction = direction;
		this.list = list;
	}
}