백준 17837 새로운 게임 2 Java 풀이

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/17837

(1) 조건 분석 📊

A. 말에 대한 규칙

1. 말은 각자 나아가려는 방향이 있다.
2. 하나의 칸에 여러 말이 있을 시, 윷놀이처럼 기존에 있던 말이 새로 해당 칸에 온 말을 업는다. (stack)
3. 하나의 말이 자신의 방향으로 움직일 때 업힌 말들도 같이 움직인다. (이떄 자신의 나아가려는 방향은 바뀌지 않는다.)
4. 말들은 자신이 나아갈 다음 칸의 색깔에 따라 행동이 미세하게 바뀐다.

B. 보드 칸 별 규칙

1. 흰 칸을 밟을 경우, 업은 말 전부 같이 움직이는 거 외에 특이 사항 없음
2. 빨간 칸을 밟을 경우, 자신을 포함한 업은 말들의 위치가 거꾸로 되어야 한다.
   (exA->B->C (TOP) 순으로 업혀 있었다면, C -> B -> A(TOP) 으로 바뀌어야 함.)
3. 파란 칸을 밟을 경우, 해당 칸으로 나아가지 않고 방향을 바꾼다.
   1. 방향을 바꿔서 한 칸 나아갔을 경우도 파란 칸을 밟는다면 움직이지 않고 다음 말 이동으로 넘어간다.
   2. 방향을 바꿔서 한 칸을 갔을 시 파란 칸이 아니라면, 해당 칸의 색깔 규칙에 맞게 움직인다.

2. 코드가 나오기까지 🛠️

KEY WORD: 시뮬레이션

알짜배기 구현이기 때문에 그대로 하면 된다. 해당 문제가 어려운 점은 문제를 풀기 위해 저장해야할 정보가 많기 때문에 실수하기 쉽다는 것이다. 이것을 명쾌하게 구분하는데만 성공했다면, 구현 자체는 어렵지 않다. 다음은 필자가 한 방식에 대한 소개일 뿐이고, 각자의 방법에 맞게 하면 되겠다.

(1) 말에 대한 정보

static class Horse {  
    int r;  
    int c;  
    int dir;  

    public Horse (int r, int c, int dir){  
        this.r = r;  
        this.c = c;  
        this.dir = dir;  
    }  
}

말의 현 위치와 나아가려는 방향은 따로 저장해두었다.

static HashMap<Integer, Horse> horse = new HashMap<>();

말의 번호는 그 말을 특정할 때 꺼내써야 함으로, HashMap의 Key로 사용했다.

(2) Board의 색깔 저장

static int [][] map; // 0 = 흰색, 1 = 빨간색, 2 = 파란색

2차원 배열로 저장했다.

(3) Board마다 존재하는 말의 상태

static ArrayList<Integer> [][] stack; // index = 0 이 맨 아래, 그 이후로부터 쌓아올라감.

색깔과 분리해서 표현했다. 2차원 배열의 좌표마다 ArrayList<Integer> 가 존재하도록 하여, '말이 업힌 상태'를 표현했다. 문제를 풀고 나서 복기해보니, (2)번과 (3)번 또한 Board라는 클래스로 묶어서 표현하는 게 더 OOP에 맞았을 것 같다.

(1) 시간복잡도 분석 ⏳

1 turn에 모든 말을 순차적으로 1회씩 움직인다.
문제에서 turn이 1000번을 넘으면 -1을 출력하라고 하였고, 말도 최대 10개라서, $10 \times 1,000 = 10,000$
이므로 시간 초과 걱정은 필요 없을 듯 하다.

3. 코드 🌐

(1) SUDO CODE 💬

1. 값 초기화
2. 하얀 칸 밟을 때 구현
3. 빨간 칸 밟을 때 구현
4. 파란 칸 밟을 때 구현
5. 1000번까지 turn을 진행
    1. 현재 움직인 말이 있는 위치에 말이 4개가 같이 있는 상태인지 확인
    2. 맞으면 turn 수 출력 후 프로그램 종류
    3. 아니면 다시 LOOP 돌기 

(2) JAVA CODE ☕

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


public class Main {  

    static class Horse {  
        int r;  
        int c;  
        int dir;  

        public Horse (int r, int c, int dir){  
            this.r = r;  
            this.c = c;  
            this.dir = dir;  
        }  
    }    static HashMap<Integer, Horse> horse = new HashMap<>();  
    static ArrayList<Integer> [][] stack; // index = 0 이 맨 아래, 그 이후로부터 쌓아올라감.  
    static int [][] map; // 0 = 흰색, 1 = 빨간색, 2 = 파란색  
    static int [][] dir = new int [][] {{-999, -999}, {0,1}, {0,-1}, {-1,0}, {1,0}};  
    static int N, K;  
    public static void main(String[] args) throws IOException {  
        init();  

        int cnt = 1;  
        while(cnt <= 1_000){  
            for(int i  = 0; i < K; i++){  
                move(i);  
                Horse now = horse.get(i);  
                if(stack[now.r][now.c].size() >= 4) {  
                    System.out.println(cnt);  
                    return;  
                }  
            }            cnt++;  
        }  
        System.out.println(-1);  
    }  

    // 움직이려는 말의 다음 위치가 흰색인지, 빨간색인지, 파란색 or 장외인지 확인 후 적절한 움직임으로 이동  
    public static void move(int index) {  
        Horse now = horse.get(index);  
        int nextR = now.r + dir[now.dir][0];  
        int nextC = now.c + dir[now.dir][1];  
        if(OOB(nextR, nextC)) goBlue(now.r, now.c, index);  
        else switch (map[nextR][nextC]){  
            case 0: {  
                goWhite(now.r, now.c, index);  
                break;  
            }  
            case 1: {  
                goRed(now.r, now.c, index);  
                break;  
            }  
            default: goBlue(now.r, now.c, index);  
        }  
    }  
    public static void goWhite(int r, int c, int index) {  
        Horse origin = horse.get(index);  
        ArrayList<Integer> now = stack[r][c];  
        ArrayList<Integer> temp = new ArrayList<>();  
        int peek = now.size()-1;  

        // stack 상 위에 것들 먼저 좌표 옮기기  
        while(now.get(peek) != index){  
            int idx = now.get(peek);  
            Horse h = horse.get(idx);  
            h.r += dir[origin.dir][0];  
            h.c += dir[origin.dir][1];  
            temp.add(idx);  
            now.remove(peek--);  
        }  
        // 내가 움직이려는 말 좌표 옮기기  
        origin.r += dir[origin.dir][0];  
        origin.c += dir[origin.dir][1];  
        temp.add(index);  
        now.remove(peek);  

        // stack에 쌓기  
        for(int i = temp.size()-1; i >= 0; i--){  
            stack[origin.r][origin.c].add(temp.get(i));  
        }  
    }  
    public static void goRed(int r, int c, int index) {  
        Horse origin = horse.get(index);  
        origin.r += dir[origin.dir][0];  
        origin.c += dir[origin.dir][1];  
        ArrayList<Integer> now = stack[r][c];  
        int peek = now.size()-1;  

        // stack 상 위에 것들 먼저 좌표 옮기기  
        while(now.get(peek) != index){  
            int idx = now.get(peek);  
            Horse h = horse.get(idx);  
            h.r += dir[origin.dir][0];  
            h.c += dir[origin.dir][1];  
            // stack에 바로 넣어야 반대로 들어감.  
            stack[origin.r][origin.c].add(idx);  
            now.remove(peek--);  
        }  
        // 내가 움직이려는 말 좌표 옮기기  
        now.remove(peek);  
        stack[origin.r][origin.c].add(index);  
    }  

    public static void goBlue(int r, int c, int index) {  
        // 방향 바꾸기  
        Horse origin = horse.get(index);  
        origin.dir = (origin.dir == 1)? 2  
            : (origin.dir == 2)? 1  
                : (origin.dir == 3)? 4  
                    : (origin.dir == 4)? 3 : 0;  

        // 방향 바꿨는데도 다음 한 칸이 blue나 OOB인지 확인  
        int nextR = origin.r + dir[origin.dir][0];  
        int nextC = origin.c + dir[origin.dir][1];  

        // 맞으면 가만히 서있기  
        if(OOB(nextR, nextC) || map[nextR][nextC] == 2) return;  
        // 아니면 이동  
        if(map[nextR][nextC] == 0) goWhite(r, c, index);  
        if(map[nextR][nextC] == 1) goRed(r, c, index);  
    }  

    public static boolean OOB (int r, int c) {  
        return r < 0 || c < 0 || r >= N || c >= N;  
    }  


    public static void init() 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][N];  
        stack = 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());  
                stack[i][j] = new ArrayList<>();  
            }  
        }  
        for(int i = 0; i < K; i++){  
            st = new StringTokenizer(br.readLine());  
            int r = Integer.parseInt(st.nextToken())-1;  
            int c = Integer.parseInt(st.nextToken())-1;  
            int dir = Integer.parseInt(st.nextToken());  
            horse.put(i, new Horse(r, c, dir));  
            stack[r][c].add(i);  
        }  
    }}

4. 트러블 슈팅 or 배운 점📝

IDE 쓰니까 바로 풀린다.
딱히 디버거를 쓴 건 아니지만, ArrayOutOfIndex가 난 위치를 알려줘서 에러 확인이 쉬워서 그런 것인거 같다. 이후에는 실전 테스트 환경에서 풀어봐야겠다.