[BOJ] 백준 17780 새로운 게임

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

 Input 
4 4
0 0 2 0
0 0 1 0
0 0 1 2
0 2 0 0
2 1 1
3 2 3
2 2 1
4 1 2

 Output 

-1

매 턴마다 말들의 위치와 상관 없이 모두 이동하는 문제: [BOJ] 17837 새로운 게임 2

[BOJ] 백준 17837 새로운 게임 2

 

 

A번 말의 이동 규칙

▶ 흰색(0)

해당 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.

A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.

ex) A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는

     A번 말이 이동한 후 D, E, A, B, C가 된다.

▶ 빨간색(1)

이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.

ex) A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.

ex) A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는

      E, C, B, G, F, D, A가 된다.

▶ 파란색(2) 

A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 

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

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

 

구현

체스판 위에 K개의 말들을 어떻게 구현할지 고민해야할 문제입니다.

// List를 이차원 배열형태로 하여 체스 말들의 번호(ID)를 저장
static ArrayList<Integer>[][] board;

// 말들의 번호(ID), 위치(x, y), 방향(dir), 이동 가능 유무(isMove)
static Horse[] horse;

// 색깔 정보
static int[][] colorMap;

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static final int WHITE = 0;
    static final int RED = 1;
    static final int BLUE = 2;
    static int N, K;
    static int[][] colorMap;
    static Horse[] horse;
    static ArrayList<Integer>[][] board;
    // → ← ↑ ↓
    static int[] dx = {0, 0, 0, -1, 1};
    static int[] dy = {0, 1, -1, 0, 0};
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
         
        // 색깔 정보와 각 칸의 말들의 정보를 초기화 
        colorMap = new int[N+1][N+1];
        board = new ArrayList[N+1][N+1];
        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++) {
                colorMap[i][j] = Integer.parseInt(st.nextToken());
                board[i][j] = new ArrayList<>();
            }
        }
        horse = new Horse[K+1];
        for(int ID=1; ID<=K; ID++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int dir = Integer.parseInt(st.nextToken());
            // 초기에는 같은 칸에 말이 두 개 이상 있는 경우 X
            horse[ID] = new Horse(ID, x, y, dir, true);
            // 체스판에 말들을 배치
            board[x][y].add(ID);
        }
         
        // 최대 1000번 동안 진행
        for(int turn = 1; turn <= 1000; turn++) {
            // 1~K개의 말들을 순차적으로 움직입니다.
            for(int idx = 1 ; idx <= K ; idx++) {
                // 1000번의 턴 중에 조건을 만족하면 종료.
                // 움직일 수 있는 말만 동작
                if(horse[idx].isMove && move(idx)) {
                    System.out.println(turn);
                    return;
                };
            }
        }
        System.out.println(-1);
    }
     
    private static boolean move(int idx) {
        Horse current = horse[idx];
         
        int nX = current.x + dx[current.dir];
        int nY = current.y + dy[current.dir];
         
        // 체스판을 벗어나거나 파란색 칸인 경우
        if(!isRangeValid(nX, nY)) {
            // 이동하는 말의 방향을 반대로 전환하여 이동하려는 칸 위치를 함께 바꿔준다.
            current.changeDirection();
            nX = current.x + dx[current.dir];
            nY = current.y + dy[current.dir];
        }
         
 
        // 체스판을 벗어나거나 파란색 칸이면 위에서 방향전환 된 것으로 continue
        // 체스판 내에서 빨간색이나 흰색칸으로 이동되는 경우
        if(isRangeValid(nX, nY)) {
            actionByColor(current, nX, nY);
            // 이동된 칸에 올려져 있는 말의 개수 확인 
            if(board[nX][nY].size() >= 4) return true;
        }
        return false;
    }
     
    private static void actionByColor(Horse current, int nX, int nY) {
        // 이동 전 말의 위치
        ArrayList<Integer> from = board[current.x][current.y];
        // 이동 후 말의 위치
        ArrayList<Integer> to = board[nX][nY];
         
        // 원소가 변하면서 size()값도 함께 변하므로 변수로 저장
        int fromSize = from.size();
         
        // 흰색 or 빨간색에 따른 처리
        switch(colorMap[nX][nY]) {
        case WHITE:
            // 이동하는 말 위에 올려져 있는 말들과 함께 이동
            for(int i = 0; i < fromSize; i++){
                // 리스트의 원소가 삭제되면서 위치가 당겨져 옵니다.
                int horseID = from.remove(0);
                // 해당 말의 좌표 변경
                horse[horseID].x = nX;
                horse[horseID].y = nY;
                horse[horseID].isMove = false;
                to.add(horseID);
            }
            // 가장 아래에 있는 말만 이동할 수 있게 설정
            horse[to.get(0)].isMove = true;
            break;
             
        case RED:
            // 이동하는 말 위에 올려져 있는 말들을 뒤집어서 함께 이동 
            for(int i = 0; i < fromSize; i++){
                // 뒤집어서 다음 위치로 이동해야 하기에 리스트 끝자리에서 삭제
                int horseID = from.remove(from.size()-1);
                // 해당 말의 좌표 변경
                horse[horseID].x = nX;
                horse[horseID].y = nY;
                horse[horseID].isMove = false;
                to.add(horseID);
            }
            // 가장 아래에 있는 말만 이동할 수 있게 설정
            horse[to.get(0)].isMove = true;
            break;
        }
    }
     
    private static boolean isRangeValid(int nX, int nY) {
        if( nX > N || nX < 1 || nY > N || nY < 1 || colorMap[nX][nY] == BLUE) {
            // 체스판을 벗어나거나 파란색 칸인 경우
            return false;
        }
        return true;
    }
}
 
class Horse{
    int ID, x, y, dir;
    boolean isMove;
     
    Horse(int ID, int x, int y, int dir, boolean isMove){
        this.ID = ID;
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.isMove = isMove;
    }
    public void changeDirection() {
        // → ← ↑ ↓
        if(dir == 1) dir = 2; 
        else if(dir == 2) dir = 1;
        else if(dir == 3) dir = 4;
        else if(dir == 4) dir = 3;
    }
}