백준 17780

문제

---

Code

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class P17780 {
	static class Node { // 말
		int num;	// 번호
		int dir;	// 방향
		Node(int num, int dir) {
			this.num = num;
			this.dir = dir;
            // 1, 2, 3, 4 : →, ←, ↑, ↓
		}
	}
	// 체스판 색 입력값
	static final int WHITE = 0;
	static final int RED = 1;
	static final int BLUE = 2;

	/*
    행과 열을 기준으로 생각했을 떼
    → : { 0, 1 }
    ← : { 0, -1 }
    ↑ : { -1, 0 }
    ↓ : { 1, 0 }
    */
	static int[][] movement = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };
	
	static int N, K;		// 체스판의 크기, 말의 개수
	static int[][] color;	// 체스판 위치별 색
	static int[][] horse;	// 체스판 말의 위치 (horse[i][j] : i행 j열)
	static LinkedList<Node>[][] board;

	static int endingTurn;
	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());

		color = new int[N][N];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < N; j++) {
				color[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		board = new LinkedList[N][N];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				board[i][j] = new LinkedList<>();
			}
		}
		horse = new int[K][2];
		for(int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			// 말 위치
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			// 말의 방향
            // movement의 index를 사용하기 위해 -1
			int c = Integer.parseInt(st.nextToken()) - 1;

			horse[i][0] = a;
			horse[i][1] = b;
			board[a][b].add(new Node(i, c));
		}
		
		playNewGame();
		
		System.out.println(endingTurn);
	}

	private static void playNewGame() {
		// 1000번 안에 끝나야 함
		for(int turn = 1; turn <= 1000; turn++) {
			// 각 턴 마다 모든 말 이동
			for(int k = 0; k < K; k++) {
				int x = horse[k][0]; // 열 위치
				int y = horse[k][1]; // 행 위치
				int dir = board[x][y].get(0).dir; // 이동방향(가장 밑의 말 기준)

				// 가장 밑의 말만 이동 가능
				if(board[x][y].get(0).num != k) {
					continue;
				}
				
				// 이동한 위치
				int newX = x + movement[dir][0];
				int newY = y + movement[dir][1];
			

				// 밖으로 나가거나 파란색 칸으로 이동한 경우
				// --> 반대로 이동
				if(outOfArea(newX, newY) || color[newX][newY] == BLUE) {
					dir = changeDirection(dir);
					board[x][y].get(0).dir = dir;
					newX = x + movement[dir][0];
					newY = y + movement[dir][1];
					
					// 반대로 이동해도 
					// 밖으로 나가거나 파란색 칸인 경우
					if(outOfArea(newX, newY) || color[newX][newY] == BLUE) {
						continue;
					} 
					// 반대로 이동해서
					// 흰색 또는 빨간색 칸인 경우
					else {
						if(move(x, y, newX, newY, color[newX][newY])) {
							endingTurn = turn;
							return;
						}
					}
				} 
				// 흰색 또는 빨간색 칸으로 이동
				else {
					if(move(x, y, newX, newY, color[newX][newY])) {
						endingTurn = turn;
						return;
					}
				}
			}
		}
		// 게임을 끝낼 수 없는 경우
		endingTurn = -1;
	}
    
    // 보드 밖으로 나간 여부
	private static boolean outOfArea(int newX, int newY) {
		return newX < 0 || newX >= N || newY < 0 || newY >= N;
	}
	
    // x열 y행에서 newX열 newY행으로 이동
    // 이동한 칸의 색이 color일 때
	private static boolean move(int x, int y, int newX, int newY, int color) {
		if(color == WHITE) { // WHITE
			// 순서대로 말 쌓기
			while(board[x][y].size() > 0) {
				Node temp = board[x][y].removeFirst();
				horse[temp.num][0] = newX;
				horse[temp.num][1] = newY;
				board[newX][newY].add(temp);
			}
		} 
		else { // RED
			// 반대 순서로 말 쌓기
			while(board[x][y].size() > 0) {
				Node temp = board[x][y].removeLast();
				horse[temp.num][0] = newX;
				horse[temp.num][1] = newY;
				board[newX][newY].add(temp);
			}
		}
		// 말이 4개 이상 쌓임--> 게임 종료
		return board[newX][newY].size() >= 4;
	}
	
    // 말의 방향 바꾸기 (나가거나 파란색 칸일때)
    // movement의 index 참고
	private static int changeDirection(int dir) {
		if(dir == 0) {
            return 1;
        }
        if(dir == 1) {
            return 0;
        }
        if(dir == 2) {
            return 3;
        }
        if(dir == 3) {
            return 2;
        }
        return 10000;
	}
}