[Java] 백준 17780 새로운 게임

문제

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.
게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.
턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동하며, 가장 아래에 있는 말만 이동할 수 있다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.

• A번 말이 이동하려는 칸이
  • 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
    • A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
    • 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.
  • 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
    • A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
    • A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.
  • 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다.
  • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

다음은 크기가 4×4인 체스판 위에 말이 4개 있는 경우이다.

 

첫 번째 턴은 다음과 같이 진행된다.

두 번째 턴은 다음과 같이 진행된다.

 

 

체스판의 크기와 말의 위치, 이동 방향이 모두 주어졌을 때, 게임이 종료되는 턴의 번호를 구해보자.
 

입력

첫째 줄에 체스판의 크기 N, 말의 개수 K가 주어진다. 둘째 줄부터 N개의 줄에 체스판의 정보가 주어진다. 체스판의 정보는 정수로 이루어져 있고, 각 정수는 칸의 색을 의미한다. 0은 흰색, 1은 빨간색, 2는 파란색이다.
다음 K개의 줄에 말의 정보가 1번 말부터 순서대로 주어진다. 말의 정보는 세 개의 정수로 이루어져 있고, 순서대로 행, 열의 번호, 이동 방향이다. 행과 열의 번호는 1부터 시작하고, 이동 방향은 4보다 작거나 같은 자연수이고 1부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다.
같은 칸에 말이 두 개 이상 있는 경우는 입력으로 주어지지 않는다.
 

출력

게임이 종료되는 턴의 번호를 출력한다. 그 값이 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력한다.
 
문제 링크 : 새로운 게임

---

설명

단순 구현 문제. 
 
이 문제에서 가장 많이 고민한 부분은 어떻게 말 위에 다른 말이 쌓여있는가를 확인하는 부분이다.
그 부분에서는 더 효율적으로도 풀 수 있었겠지만 생각이 잘 안 나서 말 번호에 따른 List를 선언해서 위에 말이 쌓일 때마다 add해주는 방식으로 구현했다.
 
그리고 빨간색 부분에서 현재 쌓여있는 말의 순서를 변경해야 하는데 그 부분도 아이디어가 그다지 떠오르지 않아 Stack으로 현재 List에 있는 말들 꺼내서 stack에 넣어주고 stack 맨 위 말을 꺼내서 다시 List에 넣어주는 식으로 구현했다.
 
아마 그 부분으로 인해서 시간이 좀 걸리지 않았나 생각해 본다. 

---

 
와 이걸로 몇 번째인지는 모르겠지만 내가 구현문제를 내 손으로 풀다니...ㅠㅠ 언제 생각해도 감격...
예전에는 아이디어만 떠오르고 그게 실제 가능한지 여부와 그걸 코드로 옮기는 게 정말 안 됐었는데 이제는 착착 생각한 대로 되니까 참 기분이 좋다. 
그럼에도 구현 문제를 풀 때 너무 시간이 오래 걸려서 더 많이 풀어봐야겠다.
생각하는 게 어렵지만 너란 친구 단순한 친구..

코드

import java.util.*;
import java.io.*;

class Main{
    static BufferedReader br;
    static int n, k , turn; // 보드판, 말 개수, 턴 개수
    static int[][] xy = {{0, 0}, {0, 1}, {0, -1}, {-1, 0}, {1, 0}}; // 오, 왼, 위, 아래
    static Horse[] horse;
    static ArrayList<Integer>[] other; // 현재 말위에 다른 말들
    static int[][] map, horseMap; // 현재 보드판, 위치에 따른 가장 아래 말 번호
    static StringTokenizer st;
    static class Horse{
        int direction, r, c; // 방향, 행, 열
        boolean down; // 가장 아래 여부

        Horse(int direction, boolean down, int r, int c){
            this.direction = direction;
            this.down = down;
            this.r = r;
            this.c = c;
        }
    }
    public static void main(String[] args)throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); k = Integer.parseInt(st.nextToken());
        map = new int[n][n]; horseMap = new int[n][n];
        turn =0;
        horse = new Horse[k +1]; // 1번말부터 시작
        other = new ArrayList[k + 1];
        for (int i = 1; i<= k; i++)
            other[i] = new ArrayList<>();

        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());
            }
        }

        for (int i = 1; i <=k; i++){
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) -1;
            int c = Integer.parseInt(st.nextToken()) -1;
            int d = Integer.parseInt(st.nextToken());
            horseMap[r][c] = i; // 말 번호
            other[i].add(i); // 본인 위 말 본인
            horse[i] = new Horse(d, true, r, c);
        }

        end : while(true){
            turn++;
            if (turn > 1000){ // 1000 넘을 시 -1 출력
                System.out.println(-1);
                return;
            }
            for (int i = 1; i <= k; i++){
                if (!horse[i].down) continue; // 본인이 가장 아래 아닌 경우
                Horse now = horse[i];
                int r = xy[now.direction][0] + now.r;
                int c = xy[now.direction][1] + now.c;
                if (r < 0 || r >= n || c < 0 || c >= n) { // 범위 벗어난 경우
                    if (blue(i, now))
                        break end;
                } else if (map[r][c] == 2){ // 이동한 블럭이 파랑색인 경우
                    if (blue(i, now))
                        break end;
                } else if (map[r][c] == 1){ // 이동한 블럭이 빨강색인 경우
                    if (red(i, now, r, c))
                        break end;
                } else { // 그 외(흰색)
                    if (white(i, now, r, c))
                        break end;
                }
            }
        }
        System.out.println(turn);
    }

    private static boolean white(int i, Horse now, int r, int c) {
        horseMap[now.r][now.c] = 0; // 기존에 있던 자리 말 없음 표시
        if (horseMap[r][c] != 0) { // 말 있는 경우
            if (other[i].size() + other[horseMap[r][c]].size() >= 4)
                return true;
            else plus(i, horseMap[r][c]);
        } else{
            horseMap[r][c] = i;
            now.r = r;
            now.c = c;
        }
        return false;
    }

    // 말 쌓는 경우
    private static void plus(int i, int origin) {
        for (Integer j : other[i])
            other[origin].add(j);
        horse[i].down = false;
    }

    private static boolean red(int i, Horse now, int r, int c) {
        int originR = now.r;
        int originC = now.c;
        if (other[i].size() > 1) { // 본인 위 말 있는 경우
            Stack<Integer> stack = new Stack<>();
            for (Integer j : other[i]) {
                stack.push(j);
            }
            now.down = false;
            horse[stack.peek()].down = true;
            i = stack.peek(); // 현재 말 변경
            other[i] = new ArrayList<>();

            while (!stack.isEmpty())
                other[i].add(stack.pop());
        }
            if (horseMap[r][c] != 0){ // 이미 말 존재
                if (other[i].size() + other[horseMap[r][c]].size() >= 4) // 말이 4개 이상 쌓인 경우
                    return true;
                else plus(i, horseMap[r][c]);
            } else { // 말 x
                horseMap[r][c] = i; // 현재 위치에 현재 말 번호 저장
                horse[i].r = r; // 말 위치 업테이트
                horse[i].c = c;
            }
        horseMap[originR][originC] = 0; // 기존 자리 말 없음 표시
        return false;
    }

    private static boolean blue(int i, Horse now) {
        if (now.direction == 1 || now.direction == 2)
            now.direction = now.direction == 1 ? 2 : 1;
        else now.direction = now.direction == 3 ? 4 : 3;

        int r = xy[now.direction][0] + now.r;
        int c = xy[now.direction][1] + now.c;
        if (r < 0 || r >= n || c < 0 || c >= n) // 범위 밖 이동 x
            return false;
        else if (map[r][c] == 2) return false; // 파랑 경우 이동 x
        else if (map[r][c] == 1){
            return red(i, now, r, c);
        }
        else return white(i, now, r, c);
    }
}