[백준 17837 / JAVA ] 새로운 게임 2

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

17837번: 새로운 게임 2

 

여러 경우의 수를 확인하고 이를 구현하는 문제이다.

 

말을 올려놓고 다시 내리고 하는 과정이 링크드리스트와 느낌이 비슷해 금방 할 줄 알았지만 생각보다 어려웠다..

 

내가 오래걸린 큰 이유는 2가지 였다.

 

1. 파란색이나 체스판을 벗어나는 경우 반대로 이동한 후 끝이 아니라 이동한 위치의 색에 따라 또 다르게 체스말을 바꿔야 한다. (빨간색인 경우 뒤집어줘야 한다)

이걸 놓치고 이동만 해줘 꽤 고생했다....

 

2. 반대로 이동 후 다음 부터 그 방향으로 가야한다.

나는 반대로 이동 후 원래 방향으로 가야하는걸로 이해해 시간이 많이 걸렸다...

 

    static ArrayList<piece> pieces = new ArrayList<piece>();

    public static class piece {
        int x, y;
        int dir;
        int upIndex;

        public piece(int x, int y, int dir) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.upIndex = -1;
        }
    }

체스말의 정보를 저장하는 piece 클래스에 좌표와 방향, 위에 있는 말의 번호를 저장한다.

클래스 객체를 연결할까 했지만 그렇게까지 하지 않아도 될 것 같아 그냥 번호만 저장했다.

 

이 체스말 객체들을 저장하는 pieces 배열을 생성했다.

 

    public static void move(int cnt) {
        int nx, ny;
        if (cnt >= 1000) {
            result = -1;
            return;
        }
        //1 오 2 왼 3위 4 아래
        for (int i = 0; i < pieces.size(); i++) {
            int pi = i;
            nx = pieces.get(i).x + dx[pieces.get(i).dir];
            ny = pieces.get(i).y + dy[pieces.get(i).dir];

            if (!(nx >= 0 && ny >= 0 && nx < N && ny < N && map[nx][ny] != 2)) { //파란색 or 범위 밖
                nx = pieces.get(i).x - dx[pieces.get(i).dir];
                ny = pieces.get(i).y - dy[pieces.get(i).dir];

                if (pieces.get(i).dir % 2 == 0) pieces.get(i).dir--;
                else pieces.get(i).dir++;
            }

            if (nx >= 0 && ny >= 0 && nx < N && ny < N && map[nx][ny] != 2) { //범위 안
                if (map[nx][ny] == 1) //빨간색
                    pi = setReverse(i); //뒤집어줌
                move(nx, ny, pi);
                int c = count(nx, ny);
                if (c >= 4) {
                    result = cnt;
                    return;
                }
            }

        }
        move(cnt + 1);
    }

    public static void move(int nx, int ny, int i) {
        int pre = findPrevious(i);//i번 아래에 있는 말 찾기
        int ni = find(nx, ny); //갈 곳에 있는 말 번호

        if (ni != -1) { //갈 곳에 말이 있음
            while (pieces.get(ni).upIndex != -1)  //가장 위 찾기
                ni = pieces.get(ni).upIndex;
            pieces.get(ni).upIndex = i;
        }

        if (pre != -1)
            pieces.get(pre).upIndex = -1;

        setPlace(i, nx, ny); //위치 바꾸기
    }

말을 이동시켜주는 메소드이다. 방향에 맞게 이동 좌표를 저장하고 이동할 체스판의 색이 파란색이거나 범위밖이면 좌표를 반대로 이동해 준다. 그 후 방향을 저장해 준다.

 

만약 범위 밖이라면 아무것도 하지 않고 범위 안이라면 이동한 체스판의 색에따라 말을 이동해준다.

다음 move 함수를 통해 이동 후 이동한 위치의 말의 수가 4 이상이라면 그만한다.

 

다음 move 함수에서는 findPrevious 메소드를 통해 이동해야 할 말 아래에 말이 있는지 찾는다.

 

find 함수를 통해 가야하는 체스판에 있는 말을 아무거나 찾는다.

가야하는 체스판 위치에 말이 있다면 그 중 가장 위 말을 찾는다.

 

이동해야 할 말의 아래에 말이 있었다면 그 말의 upIndex를 -1로 바꿔 없도록 바꿔준다.

 

setPlace 함수를 통해 말의 위치를 바꿔준다.

 

    public static int find(int x, int y) {
        for (int i = 0; i < pieces.size(); i++) {
            if (pieces.get(i).x == x && pieces.get(i).y == y)
                return i;
        }
        return -1;
    }

해당 좌표에 있는 아무 체스말을 가져온다

 

    public static int findPrevious(int index) {
        for (int i = 0; i < pieces.size(); i++) {
            if (pieces.get(i).upIndex == index)
                return i;
        }
        return -1;
    }

해당 인덱스의 체스말에 바로 아래에 있는 체스말의 번호를 가져온다.

 

    public static int count(int x, int y) {
        int cnt = 0;
        for (int i = 0; i < pieces.size(); i++) {
            if (pieces.get(i).x == x && pieces.get(i).y == y)
                cnt++;
        }
        return cnt;
    }

해당 좌표에 있는 체스말의 갯수를 가져온다.

 

    public static int setReverse(int index) {
        int next, now = index, pre = index;
        int pi = findPrevious(index); //i번 아래에 있는 말 찾기

        next = pieces.get(index).upIndex;
        pieces.get(index).upIndex = -1;
        while (next != -1) {
            now = next;
            next = pieces.get(now).upIndex;
            pieces.get(now).upIndex = pre;
            pre = now;
        }
        if (pi != -1)
            pieces.get(pi).upIndex = now;
        return now;
    }

해당 인덱스의 체스말부터 위에 있는 모든 체스말들을 서로 뒤집는다.

 

    public static void setPlace(int index, int nx, int ny) {
        pieces.get(index).x = nx;
        pieces.get(index).y = ny;
        if (pieces.get(index).upIndex != -1)
            setPlace(pieces.get(index).upIndex, nx, ny);
    }

해당 인덱스의 말을 입력받은 좌표로 바꾼다. 해당 말의 위에 있는 말들도 모두 바꾼다.

반응형

 

전체 코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int N, K, result;
    static int[][] map;
    static int[] dx = {0, 0, 0, -1, 1}, dy = {0, 1, -1, 0, 0};

    static ArrayList<piece> pieces = new ArrayList<piece>();

    public static class piece {
        int x, y;
        int dir;
        int upIndex;

        public piece(int x, int y, int dir) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.upIndex = -1;
        }
    }

    public static void move(int cnt) {
        int nx, ny;
        if (cnt >= 1000) {
            result = -1;
            return;
        }
        //1 오 2 왼 3위 4 아래
        for (int i = 0; i < pieces.size(); i++) {
            int pi = i;
            nx = pieces.get(i).x + dx[pieces.get(i).dir];
            ny = pieces.get(i).y + dy[pieces.get(i).dir];

            if (!(nx >= 0 && ny >= 0 && nx < N && ny < N && map[nx][ny] != 2)) { //파란색 or 범위 밖
                nx = pieces.get(i).x - dx[pieces.get(i).dir];
                ny = pieces.get(i).y - dy[pieces.get(i).dir];

                if (pieces.get(i).dir % 2 == 0) pieces.get(i).dir--;
                else pieces.get(i).dir++;
            }

            if (nx >= 0 && ny >= 0 && nx < N && ny < N && map[nx][ny] != 2) { //범위 안
                if (map[nx][ny] == 1) //빨간색
                    pi = setReverse(i); //뒤집어줌
                move(nx, ny, pi);
                int c = count(nx, ny);
                if (c >= 4) {
                    result = cnt;
                    return;
                }
            }

        }
        move(cnt + 1);
    }

    public static void move(int nx, int ny, int i) {
        int pre = findPrevious(i);//i번 아래에 있는 말 찾기
        int ni = find(nx, ny); //갈 곳에 있는 말 번호

        if (ni != -1) { //갈 곳에 말이 있음
            while (pieces.get(ni).upIndex != -1)  //가장 위 찾기
                ni = pieces.get(ni).upIndex;
            pieces.get(ni).upIndex = i;
        }

        if (pre != -1)
            pieces.get(pre).upIndex = -1;

        setPlace(i, nx, ny); //위치 바꾸기
    }


    public static int find(int x, int y) {
        for (int i = 0; i < pieces.size(); i++) {
            if (pieces.get(i).x == x && pieces.get(i).y == y)
                return i;
        }
        return -1;
    }

    public static int findPrevious(int index) {
        for (int i = 0; i < pieces.size(); i++) {
            if (pieces.get(i).upIndex == index)
                return i;
        }
        return -1;
    }

    public static int count(int x, int y) {
        int cnt = 0;
        for (int i = 0; i < pieces.size(); i++) {
            if (pieces.get(i).x == x && pieces.get(i).y == y)
                cnt++;
        }
        return cnt;
    }

    public static int setReverse(int index) { //2
        int next, now = index, pre = index;
        int pi = findPrevious(index); //i번 아래에 있는 말 찾기

        next = pieces.get(index).upIndex;
        pieces.get(index).upIndex = -1;
        while (next != -1) {
            now = next; //0 1
            next = pieces.get(now).upIndex; //1 -1
            pieces.get(now).upIndex = pre; //2
            pre = now;
        }
        if (pi != -1)
            pieces.get(pi).upIndex = now;
        return now;
    }

    public static void setPlace(int index, int nx, int ny) {
        pieces.get(index).x = nx;
        pieces.get(index).y = ny;
        if (pieces.get(index).upIndex != -1)
            setPlace(pieces.get(index).upIndex, nx, ny);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

        map = new int[N][];
        for (int i = 0; i < N; i++) {
            map[i] = new int[N];
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < K; i++)
            pieces.add(new piece(sc.nextInt() - 1, sc.nextInt() - 1, sc.nextInt()));

        move(1);
        System.out.println(result);
    }
}