[백준 / BOJ] 17780 새로운 게임 (Java)

문제

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

17780번: 새로운 게임

 

(...)

---

풀이

문제에서 주어진 그대로 풀면되는 시뮬레이션 문제였다.

 

문제 해석시 주의할점이 있었는데,

 

1. 다음 위치가 빨간색인데, 이동할 위치에 이미 다른 체스말들이 있는경우, 이동후 체스말을 위로 쌓은다음에 체스말의 순서를 뒤집는것이 아니라, 이동 전에 뒤집고 체스말을 위로 쌓는것이다.

예를들어, 현재 이동할 체스말들이 (1,2,3) 순서대로 쌓여있고 이동위치에 이미 (4,5)체스말이 쌓여있다면, 이동후 체스말의 상태는

(4,5,3,2,1)이 된다. 

 

2. 현재 이동방향이 -> 이며, 현재위치의 체스판색이 빨강, 다음위치가 파랑, <- 위치가 파랑일때,

예를들어,

파랑색(1)

빨강색 (현재위치) (이동 ->)

파랑색(2)

위와 같은 상태에서, 이동하면 파랑색(1)위치로 이동할수없으니 방향만 바꾸고 이동하지않는다.

즉, 이동하지않으므로 빨강색에 있는 체스말들의 순서를 바꾸면 안된다. (1,2,3)순서였다면 이 순서 그대로 방향만 바꿔줘야함.

구현 

소스코드에 주석이 달려있으니 바로 전체코드를 봐도 상관없다.

 

Chess

class Chess{ // 체스 말
    public int y, x, dir, serial;
    public Chess(int serial, int y, int x, int dir){
        set(y, x, dir);
        this.serial = serial;
    }
    
    public void set(int y, int x, int dir){
        this.y = y;
        this.x = x;
        this.dir = dir;
    }
    
    public void reverseDir(){
        dir = Solve.dir[dir];
    }
    
}

우선, 각 체스말들을 표현하는 클래스 Chess를 선언했다.

Chess에는

현재위치 y,x,

방향 dir

체스번호 serial 이 들어있다.

 

ChessMen

class ChessMen{ // 쌓여있는 체스말
    public ArrayList<Chess> chessMen = new ArrayList<Chess>();
    
    public boolean add(Chess chess){
        if(chessMen.size() >= 3) return false; // 이미 3개이상 쌓여있으면 이번에 쌓았을때 4개가 쌓이는것이므로 바로 종료해줌
        chessMen.add(chess);
        return true;
    }
    
    private void reverse(){
        Chess temp = new Chess(chessMen.get(0).serial, chessMen.get(0).y, chessMen.get(0).x, chessMen.get(0).dir);
        chessMen.set(0,chessMen.get(chessMen.size()-1));
        chessMen.set(chessMen.size()-1, temp);
    }
    
    public int findSerial(int serial){
        for(int i = 0; i < chessMen.size(); i++){
            if(chessMen.get(i).serial == serial) return i;
        }
        return -1;
    }
    
    public int move(){ // 삭제 요청 = -1, 종료 요청 = -2
        Chess chess = chessMen.get(0);
        int nextY = chess.y + Solve.dy[chess.dir];
        int nextX = chess.x + Solve.dx[chess.dir];
        if(Solve.arr[nextY][nextX] == 1){ // 다음 위치가 빨강
            reverse();
            Solve.chessBoard[chess.y][chess.x] = null;
            if(Solve.chessBoard[nextY][nextX] != null){ // 이미 해당위치에 있다면
                update(nextY, nextX); // 먼저 업데이트하고 붙여주자.
                Solve.chessBoard[nextY][nextX].chessMen.addAll(this.chessMen); // 해당위치에 있는 ChessMen에 이 chessMen을 붙인다.
                if(Solve.chessBoard[nextY][nextX].chessMen.size() > 3) return -2;
                return -1;
            }
            else Solve.chessBoard[nextY][nextX] = this;
            update(nextY, nextX);
        }
        else if(Solve.arr[nextY][nextX] == 2 || nextY > Solve.N || nextY < 1 || nextX > Solve.N || nextX < 1){ // 다음 위치가 파랑
            chess.reverseDir(); // 방향 변경
            nextY = chess.y + Solve.dy[chess.dir];
            nextX = chess.x + Solve.dx[chess.dir]; // 다음위치 계산
            if(Solve.arr[nextY][nextX] == 2 || nextY > Solve.N || nextY < 1 || nextX > Solve.N || nextX < 1){ // 방향 변경후 이동위치가 다시 파랑색이라면,
                return 0; // 이동하지않고, 방향만 바꾼다. 이동하지않았으니 현재위치가 빨간색이더라도 reverse()해주면 안된다.
            }
            else if(Solve.arr[nextY][nextX] == 1){ // 방향 변경후 이동위치라 빨간색이라면,
                reverse(); // 순서를 바꾼다.
                Solve.chessBoard[chess.y][chess.x] = null; // 현재위치를 null로 변경한다
                if(Solve.chessBoard[nextY][nextX] != null){ // 이미 해당위치에 있다면
                    update(nextY,nextX); // 먼저 업데이트하고 붙여주자.
                    Solve.chessBoard[nextY][nextX].chessMen.addAll(this.chessMen); // 해당위치에 있는 ChessMen에 이 chessMen을 붙인다.
                    if(Solve.chessBoard[nextY][nextX].chessMen.size() > 3) return -2;
                    return -1;
                }
                else Solve.chessBoard[nextY][nextX] = this;
                update(nextY,nextX);
            }
            else{ // 방향 변경후 이동위치가 흰색이라면,
                Solve.chessBoard[chess.y][chess.x] = null;
                if(Solve.chessBoard[nextY][nextX] != null){ // 이미 해당위치에 있다면
                    update(nextY,nextX); // 먼저 업데이트하고 붙여주자.
                    Solve.chessBoard[nextY][nextX].chessMen.addAll(this.chessMen); // 해당위치에 있는 ChessMen에 이 chessMen을 붙인다.
                    if(Solve.chessBoard[nextY][nextX].chessMen.size() > 3) return -2;
                    return -1;
                }
                else Solve.chessBoard[nextY][nextX] = this;
                update(nextY,nextX);
            }
        }
        else{ // 다음 위치가 흰색
            Solve.chessBoard[chess.y][chess.x] = null;
            if(Solve.chessBoard[nextY][nextX] != null){ // 이미 해당위치에 쌓여있는 체스말이 있다면
                update(nextY,nextX); // 먼저 업데이트하고 붙여주자.
                Solve.chessBoard[nextY][nextX].chessMen.addAll(this.chessMen); // 해당위치에 있는 ChessMen에 이 chessMen을 붙인다.
                if(Solve.chessBoard[nextY][nextX].chessMen.size() > 3) return -2;
                return -1;
            }
            else Solve.chessBoard[nextY][nextX] = this;
            update(nextY,nextX);
        }
        return 0;
    }

체스말들이 쌓여있는 상태를 표현할 ChessMen을 선언한다. (ChessMen이 스파게티코드라 좀 길다.)

이동은 항상 ChessMen단위로 움직일것이다.

ChessMen에는 add, move, findSerial, reverse 메소드가 있다.

 

1. add() :  (만들고 거의 사용안함) ChessMen에 원소를 추가하는 역할을 하는데, 막상 구현때는(체스단위로 넣을일이 거의 없어서) ArrayList의 addAll()을 사용했다,,

 

2. findSerial() : Solve(아래나옴) 클래스에서 체스를 찾을때 사용하는 메소드이다. 현재 chessMen에 쌓여있는 체스중 해당 serial을 가진 체스가 있으면 idx를 반환한다. 이때, 아래에있지않으면(반환 인덱스가 0이 아니라면) 이동하지않는다.

 

3. reverse() : 빨강색 칸에 갔을때, 가장아래 체스말과 가장위의 체스말을 바꿔준다.(모든 체스말을 바꿀필요는 없다는것에 주의하자)

 

4. move() : 움직임을 담당하는 메소드이다. 빨강 파랑 흰색일때를 구분해서 구현했다. (이곳이 스파게티,, 함수로 묶을까 고민했지만 구현실수 할까봐 그만뒀다)

 

Solve

class Solve{
    
    private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private ArrayList<ChessMen> chessMen = new ArrayList<ChessMen>();
    public static int N, K;
    public static int[][] arr = new int[15][15];
    public static ChessMen[][] chessBoard = new ChessMen[15][15];
    public static int[] dy = {0, 0, 0, -1, 1};
    public static int[] dx = {0, 1, -1, 0, 0};
    public static int[] dir = {0, 2, 1, 4, 3};
    
    public void run() throws Exception{
        input();
        System.out.println(game(1));
    }
    
    private void input() throws Exception{
        String[] temp = br.readLine().split(" ");
        N = Integer.parseInt(temp[0]);
        K = Integer.parseInt(temp[1]);
        for(int i = 1; i <= N; i++){
            temp = br.readLine().split(" ");
            for(int j = 0; j < N; j++) arr[i][j+1] = Integer.parseInt(temp[j]);
        }
        ChessMen trashChessMen = new ChessMen();
        chessMen.add(trashChessMen);
        for(int i = 1; i <= K; i++){
            temp = br.readLine().split(" ");
            int y = Integer.parseInt(temp[0]);
            int x = Integer.parseInt(temp[1]);
            int dir = Integer.parseInt(temp[2]);
            Chess chess = new Chess(i,y,x,dir);
            ChessMen chessMen = new ChessMen();
            chessMen.add(chess);
            this.chessMen.add(chessMen);
            chessBoard[y][x] = chessMen;
        }
    }
    private int game(int turn){
        if(turn > 1000) return -1;
        for(int i = 1; i <= K; i++){
            ChessMen ans = null;
            for(int j = 1; j <= chessMen.size()-1; j++){
                if(chessMen.get(j).findSerial(i) == 0) ans = this.chessMen.get(j);
            }
            if(ans != null){ // 가장 아래에있다면
                int move = ans.move();
                if(move == -1){ // 움직였는데 삭제요청이 들어오면,
                    chessMen.remove(ans); // 삭제
                }
                if(move == -2) return turn; // 종료 요청이 들어오면 종료
            }
        }
        return game(turn+1);
    }
    
}

실질적으로 문제를 푸는 클래스이다.

메인 함수에서 Solve의 run을 호출하면, 입력을받고 문제를 풀기 시작한다.

input() : 입력을 받는 메소드이다.

game() : 문제를 푸는 메소다. turn을 늘려가며 1번부터 K번 체스말까지 전부 확인한다. 해당 체스말이 본인이 쌓여있는곳에서 가장 아래에 위치한다면, 이동시킨다.

 

---

(엄청난 길이의 소스코드)

코드는 길지만 읽기 어렵지 않을것이다.. 아마도..?

사바사지만 자바로 푸니까 C로 풀때보다 구현실수가 확실히 줄어든것같다 (코드짜는데 시간은 확실히 더 오래걸림)

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/17780%20%EC%83%88%EB%A1%9C%EC%9A%B4%20%EA%B2%8C%EC%9E%84/Main.java

devxb/JJUNalgo