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

 

문제

 

www.acmicpc.net/problem/17780

17780번: 새로운 게임

 

풀이

 

 

크게 체스판에 대한 데이터, 체스말(Node)에 대한 데이터, 쌓여있는 체스말에 대한 데이터를 어떻게 저장할 것인지 고민했다.

- 체스판에 대한 데이터(빨, 파, 흰)는 2차원 int 배열로 입력 받는 그대로 저장한다.

- 체스말에 대한 데이터는  x, y좌표 값과 방향 값을 필드 데이터로 갖는 Node 객체를 생성해 ArrayList에 저장하였다. (방향 별 이동을 쉽게 하기 위해 dir_x, dir_y 배열을 만들었다.)

- 쌓여있는 체스말에 대한 정보는 2차원 Deque 배열로 체스말의 번호를 저장하였다. (빨간 벽일 때는 스택처럼, 흰 벽일 때는 Queue처럼 이용해야 하기 때문에 두 가지를 합친 자료구조인 Deque를 이용하기로 결정했다.)

 

구현하기가 복잡하지 흐름은 단순했다.

1. node리스트를 처음부터 순차적으로 탐색해 이동 여부를 체크한다.

- 해당 node가 가장 밑에 깔린 체스말이 아닌 경우, 즉 dequeMap[x][y].firstPeek() != i 인 경우는 skip한다.

- 방향 값을 인덱스 삼아 dir_x, dir_y를 이용해 new_x, new_y 좌표 값을 구한다.

- map[new_x][new_y]를 통해 해당 칸의 색을 확인한다.

 

2-1. 범위 밖이거나 파란색 칸인 경우

- 뱡향을 180도 돌린다.(90도가 아닌 180도이기 때문에 주의한다.)

- 새로운 방향으로 한 칸 이동하는데 1부터 다시 처리한다. (이 때 이동한 곳이 2-1에 해당하는 경우는 이동하지 않는다.)

 

2-2. 흰색인 경우

- 기존 칸인 dequeMap[x][y]에 있는 값을 앞에서부터 모두 꺼내 dequeMap[new_x][new_y] 끝부터 추가한다. (Queue 방식)

- deque에는 체스말의 index값이 들어있다. index를 통해 node리스트에 접근하여 해당 체스말들의 좌표도 new_x, new_y로 업데이트 한다.

 

2-3. 빨간색 인경우

- 기존 칸인 dequeMap[x][y]에 있는 값을 뒤에서부터 모두 꺼내 dequeMap[new_x][new_y] 끝부터 추가한다. (Stack 방식)

- deque에는 체스말의 index값이 들어있다. index를 통해 node리스트에 접근하여 해당 체스말들의 좌표도 new_x, new_y로 업데이트 한다.

 

3. dequeMap[new_x][new_y] 사이즈가 4이상이면 count를 출력하고 종료한다.

- count >1000이 될 때까지 while문 연산을 반복하고 종료가 되면 -1을 출력한다. 

 

방법을 생각해내는데는 어려움이 없었지만 조건들이 많다보니 자잘한 실수 때문에 시간이 오래 걸렸다. 실제 시험에 이런 문제가 나온다면 정신을 똑띠 차리지 않으면 다른 문제까지 영향을 줄 수 있으니 주의하자.

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static final int WHITE = 0;
    private static final int RED = 1;
    private static final int BLUE = 2;
    private static int[] dir_x = {0, 0, -1, 1};
    private static int[] dir_y = {1, -1, 0, 0};

    private static int N;
    private static int K;
    private static int[][] map;
    private static Deque<Integer>[][] dequeMap;
    private static List<Node> nodes = new ArrayList<>();


    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];
        dequeMap = new ArrayDeque[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());
                dequeMap[i][j] = new ArrayDeque<>();
            }
        }

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            int dir = (Integer.parseInt(st.nextToken()) + 3) % 4;

            nodes.add(new Node(x, y, dir));
            dequeMap[x][y].offer(i);
        }

        int count = 1;

        while (count <= 1000) {

            for (int i = 0; i < K; i++) {
                Node node = nodes.get(i);

                int x = node.x;
                int y = node.y;

                if (dequeMap[x][y].getFirst() != i) {
                    continue;
                }

                int new_x = x + dir_x[node.dir];
                int new_y = y + dir_y[node.dir];

                if (!isInArea(new_x, new_y) || map[new_x][new_y] == BLUE) {
                    int new_dir = (node.dir + 1) % 2;

                    if (node.dir >= 2) {
                        new_dir += 2;
                    }

                    new_x = x + dir_x[new_dir];
                    new_y = y + dir_y[new_dir];

                    if (!isInArea(new_x, new_y) || map[new_x][new_y] == BLUE) {
                        new_x = x;
                        new_y = y;

                    } else if (map[new_x][new_y] == RED) {
                        moveStackInCaseOfRed(x, y, new_x, new_y, i, node);
                    } else {
                        moveStackInCaseOfWhite(x, y, new_x, new_y, i, node);
                    }

                    nodes.set(i, new Node(new_x, new_y, new_dir));

                } else if (map[new_x][new_y] == WHITE) {
                    moveStackInCaseOfWhite(x, y, new_x, new_y, i, node);
                } else if (map[new_x][new_y] == RED) {
                    moveStackInCaseOfRed(x, y, new_x, new_y, i, node);
                }

                if (dequeMap[new_x][new_y].size() >= 4) {
                    System.out.println(count);
                    return;
                }
            }

            count++;
        }

        System.out.println(-1);
    }

    private static void moveStackInCaseOfWhite(int x, int y, int new_x, int new_y, int i, Node node) {
        while (!dequeMap[x][y].isEmpty()) {
            int index = dequeMap[x][y].pollFirst();
            nodes.set(index, new Node(new_x, new_y, nodes.get(index).dir));

            dequeMap[new_x][new_y].offer(index);
        }

        nodes.set(i, new Node(new_x, new_y, node.dir));
    }

    private static void moveStackInCaseOfRed(int x, int y, int new_x, int new_y, int i, Node node) {
        while (!dequeMap[x][y].isEmpty()) {
            int index = dequeMap[x][y].pollLast();
            nodes.set(index, new Node(new_x, new_y, nodes.get(index).dir));

            dequeMap[new_x][new_y].offer(index);
        }

        nodes.set(i, new Node(new_x, new_y, node.dir));
    }

    private static boolean isInArea(int x, int y) {
        return x >= 0 && y >= 0 && x < N && y < N;
    }

    static class Node {
        private int x;
        private int y;
        private int dir;

        public Node(int x, int y, int dir) {
            this.x = x;
            this.y = y;
            this.dir = dir;
        }
    }
}