[BOJ]17780.새로운 게임(시뮬레이션).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

생각보다 조건이 까다로운.. 문제다

조건을 먼저 살펴보면

* 하나의 말 위에 다른 말을 올릴 수 있다.

* 턴 한 번은 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번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 

   방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다.

- 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

...

조건이 참 많다..ㅋㅋㅋㅋ

그래서 단계별로 먼저 어떻게 구현할지 밑그림을 그리고 시작해야한다.

1. 먼저 체스판 위에 말들을 세운다

2. 매 턴마다 1번 말부터 K번 말까지 순서대로 이동하게된다.

- 여기서 턴이 1000 이상이 되면 절대로 게임이 종료되지 않는 경우고 -1 출력

- 말이 가장 아래에 있지 않다면 pass

3. 말이 자신의 방향으로 이동한다

4. 다음 칸이 체스판을 벗어나거나 파란색 칸에 왔을 경우, 말의 이동 방향을 반대로 하고 한 칸 이동,

- 한 칸 이동한 곳이 또 다시 체스판을 벗어나거나 파란색 칸일 경우는 이동하지 않고 방향만 반대로 바꾼다.

- 그렇지 않고 이동한 다음 칸이 빨간색 칸일 경우 해당 말과 그 위에 있는 모든 말이 쌓인 순서를 반대로 바꾼다.

5. 다음 칸이 흰색 칸일경우, 그 칸으로 이동

6. 다음 칸이 빨간 칸일 경우, 해당 말과 그 위에 있는 모든 말이 쌓인 순서를 반대로 바꾼다.

밑그림을 그렸으니 가장 중요한 구현을 해보자!

#. Code_v1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ17780 {
 
    static int N, K, map[][], place[][][], piece[][], floor[];
    static int[] dx = {0, 0, -1, 1}, dy = {1, -1, 0, 0};
    
    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());    // 말의 개수
        map = new int[N][N];
        place = new int[5][N][N];    // 말 위치 정보 1층~4층
        piece = new int[K + 1][3];    // 말 정보, 행,열,방향
        floor = new int[K + 1];    // 말이 몇 층에 있는지
        // 체스판 정보 입력
        // 0은 흰색, 1은 빨간색, 2는 파란색
        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());
            piece[i][0] =  Integer.parseInt(st.nextToken()) - 1; // 행
            piece[i][1] =  Integer.parseInt(st.nextToken()) - 1; // 열
            piece[i][2] =  Integer.parseInt(st.nextToken()) - 1; // 이동 방향
            // 같은 칸에 말이 두 개 이상 있는 경우는 입력으로 주어지지 않는다.
            floor[i] = 1;
            place[1][piece[i][0]][piece[i][1]] = i;
        }
        
        int turn = 0;
        out: while(true) {
            ++turn;
            if(turn >= 1000) {
                turn = -1;
                break out;
            }
            
            // 턴 한 번은 1번 말부터 K번 말까지 순서대로 이동
            for (int k = 1; k <= K; k++) {
                // 말이 가장 아래에 있지 않다면 pass
                if(floor[k] != 1) continue;
                
                int x = piece[k][0];
                int y = piece[k][1];
                
                // k번 말이 이동
                int xx = x + dx[piece[k][2]];
                int yy = y + dy[piece[k][2]];
        
                // 체스판을 벗어나는 경우 or 파란색일 경우
                if(xx < 0 || yy < 0 || xx >= N || yy >= N || map[xx][yy] == 2) {
                    // k번 말의 이동 방향을 반대로 하고 한 칸 이동
                    if(piece[k][2] < 2) 
                        piece[k][2] = piece[k][2] == 0 ? 1 : 0; 
                    else 
                        piece[k][2] = piece[k][2] == 2 ? 3 : 2;
                    
                    xx = x + dx[piece[k][2]];
                    yy = y + dy[piece[k][2]];
                    
                    // 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 
                    if(xx < 0 || yy < 0 || xx >= N || yy >= N || map[xx][yy] == 2) {
                        // 이동하지 않고 방향만 반대로 바꾼다.
                        if(piece[k][2] < 2) 
                            piece[k][2] = piece[k][2] == 0 ? 1 : 0; 
                        else 
                            piece[k][2] = piece[k][2] == 2 ? 3 : 2;
                        
                        continue;
                    }
                    // 빨간색인경우
                    if(map[xx][yy] == 1) {
                        reverse(x, y);
                    }
                    
                    if(!move(xx, yy, k)) break out;
                }
                // 흰색인 경우에는 그 칸으로 이동
                else if(map[xx][yy] == 0) {
                    
                    if(!move(xx, yy, k)) break out;
                    
                } 
                else if(map[xx][yy] == 1) {
                    // 빨간색인 경우에는 이동한 후에 
                    // A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다
                    // 말이 몇 개나 쌓였나 확인
                    reverse(x, y);
                    
                    // 이동시키자
                    if(!move(xx, yy, k)) break out;
                }
 
            }
            
        }
 
        System.out.println(turn);
    }
    
    private static void reverse(int x, int y) {
        
        int idx = 1;
        while(true) {
            if(place[idx][x][y] != 0) idx++;
            else break;
        }
        // 순서를 바꾸고
        idx--;
        if(idx == 2) {
            floor[place[1][x][y]] = 2;
            floor[place[2][x][y]] = 1;
            
            int tmp = place[1][x][y];
            place[1][x][y] = place[2][x][y];
            place[2][x][y] = tmp;
        } else if(idx == 3) {
            floor[place[1][x][y]] = 3;
            floor[place[3][x][y]] = 1;
            
            int tmp = place[1][x][y];
            place[1][x][y] = place[3][x][y];
            place[3][x][y] = tmp;
        }
 
    }
    
    static private boolean move(int xx, int yy, int k) {
        
        int x = piece[k][0];
        int y = piece[k][1];
        
        // 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
        if(place[1][xx][yy] != 0) {
            // 몇 층에 말을 올릴 수 있는지 확인
            int idx = 2;
            while(true) {
                if(place[idx][xx][yy] != 0) idx++;
                else break;
            }
            // idx 층에 말을 올릴 수 있음.
            // 말이 4개 이상 쌓이는 순간 게임이 종료
            if(idx == 4) return false;
            
            // 그렇지 않을 경우 말을 쌓자(1층~3층까지 확인)
            for (int i = 1; i <= 3; i++) {
                // 말이 있다면 쌓자
                if(place[i][x][y] != 0) {
                    floor[place[i][x][y]] = idx;
                    
                    piece[place[i][x][y]][0] = xx;
                    piece[place[i][x][y]][1] = yy;
                    
                    place[idx++][xx][yy] = place[i][x][y];
                    place[i][x][y] = 0;
 
                    if(idx > 4) return false;
                }
                else break;
            }
        } else {
            // 칸에 말이 없을 경우 말을 위치시키자.
            int idx = 1;
            // 그렇지 않을 경우 말을 쌓자(1층~3층까지 확인)
            for (int i = 1; i <= 3; i++) {
                // 말이 있다면 쌓자
                if(place[i][x][y] != 0) {
                    floor[place[i][x][y]] = idx;
                    
                    piece[place[i][x][y]][0] = xx;
                    piece[place[i][x][y]][1] = yy;
                    
                    place[idx++][xx][yy] = place[i][x][y];
                    place[i][x][y] = 0;
                }
                else break;
            }
        }
 
        return true;
    }
 
}
 

#. Code_v2

2차원 ArrayList를 사용하면 이동하는 말들을 관리하기 더 편리하다.

2차원 ArrayList, 2차원 Queue를 사용해야하는 문제들이 앞으로 많이 출제된다고 하니..

참고해두자!

/*
* reference : skygood95
*/
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class BOJ17780_v2 {
 
    static int N, K, map[][];
    static int dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
    static ArrayList<Integer> s[][];
    static piece num[];
 
    public static class piece {
        int x;
        int y;
        int d;
 
        public piece(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
 
    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()); // 말의 개수
        map = new int[N + 1][N + 1];
        num = new piece[K];
        s = new ArrayList[N + 1][N + 1];
        // 체스판 정보 입력
        // 0은 흰색, 1은 빨간색, 2는 파란색
        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());
                s[i][j] = new ArrayList<Integer>();
            }
        }
        // 말 정보 입력
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()); // 행
            int y = Integer.parseInt(st.nextToken()); // 열
            int d = Integer.parseInt(st.nextToken()); // 이동방향
            if (d == 1) {
                d = 1;
             } else if (d == 2) {
                d = 3;
             } else if (d == 3) {
                d = 0;
             } else if (d == 4) {
                d = 2;
             }
            // 같은 칸에 말이 두 개 이상 있는 경우는 입력으로 주어지지 않는다.
            num[i] = new piece(x, y, d);
            s[x][y].add(i);
        }
 
        System.out.println(start());
    }
 
    private static int start() {
 
        int time = 1;
 
        while (time <= 1000) {
            for (int i = 0; i < K; i++) {
                piece next = num[i];
                int x = next.x;
                int y = next.y;
                
                // 말이 가장 아래에 있지 않다면 pass
                if (s[next.x][next.y].get(0) != i)
                    continue;
                
                // 말이 이동
                int x1 = next.x + dir[next.d][0];
                int y1 = next.y + dir[next.d][1];
                
                // 다음 칸이 체스판을 벗어나는 경우 or 파란색일 경우
                if (x1 < 1 || x1 > N || y1 < 1 || y1 > N || map[x1][y1] == 2) {
                    // k번 말의 이동 방향을 반대로 하고 한 칸 이동
                    next.d = (next.d + 2) % 4; 
                    x1 = next.x + dir[next.d][0];
                    y1 = next.y + dir[next.d][1];
                    
                    // 방향을 반대로 한 후에 이동하려는 칸이 체스판을 벗어나는 경우 or 파란색일 경우
                    if (x1 < 1 || x1 > N || y1 < 1 || y1 > N || map[x1][y1] == 2) {
                        // 이동하지 않고 방향만 반대로 바꾼다.
                        next.d = (next.d + 2) % 4;
                    } else if (map[x1][y1] == 0) {
                        if(!move(next, x1, y1)) 
                            return time;
                    } else {
                        // 방향을 반대로 한 후에 이동하려는 칸이 빨간칸일 경우
                        if(!reverse(next, x1, y1)) 
                            return time;
                    }
                } // 다음 칸이 흰색칸일 경우 그냥 이동
                else if (map[x1][y1] == 0) {
                    if(!move(next, x1, y1)) 
                        return time;
                } // 다음 칸이 빨간칸일 경우
                else {
                    if(!reverse(next, x1, y1)) 
                        return time;
                }
            }
            
            time++;
        }
        
        return -1;
    }
    
    private static boolean reverse(piece next, int x1, int y1) {
        
        int x = next.x;
        int y = next.y;
        
        while (s[x][y].size() != 0) {
            int nextnum = s[next.x][next.y].remove(s[next.x][next.y].size() - 1);
            num[nextnum].x = x1;
            num[nextnum].y = y1;
            s[x1][y1].add(nextnum);
        }
        if (s[x1][y1].size() >= 4) {
            return false;
        }
        
        return true;
    }
    
    static private boolean move(piece next, int x1, int y1) {
        
        // 방향을 반대로 한 후에 이동하려는 칸이 흰색칸일 경우
        Stack<Integer> ne = new Stack<Integer>();
        while (s[next.x][next.y].size() != 0) {
            ne.add(s[next.x][next.y].remove(s[next.x][next.y].size() - 1));
        }
        while (!ne.isEmpty()) {
            int nextnum = ne.pop();
            num[nextnum].x = x1;
            num[nextnum].y = y1;
            s[x1][y1].add(nextnum);
        }
        if (s[x1][y1].size() >= 4) {
            return false;
        }
        
        return true;
    }
}