내용 자체는 까다롭지 않았지만, 구현하다가 보면 실수하기가 쉬운 부분이 많이 있어 보이는 문제였습니다.

까다롭지 않았지만 까다로운 문제였다 라는 생각이 들었습니다.

이번 문제를 해결하면서 몇가지 알게된 사실이 있습니다.

1. 배열안에 리스트를 넣는 방법

List<Integer>[][]

2. sublist 를 list안에 바로 넣지를 못하기 때문에 새로운 list를 만들어 주고 그안에 sublist를 넣은 다음에 할당

horse_current_position[current_row][current_col] = new ArrayList<>(current_tile_horses
    .subList(0, j));

문제는 아래 백준 사이트에서 풀어볼 수 있습니다.

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

17837번: 새로운 게임 2

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하

www.acmicpc.net

새로운 게임 2

문제

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.

게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.

턴 한 번은 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번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다.
- 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

입력

첫째 줄에 체스판의 크기 N, 말의 개수 K가 주어진다. 둘째 줄부터 N개의 줄에 체스판의 정보가 주어진다. 체스판의 정보는 정수로 이루어져 있고, 각 정수는 칸의 색을 의미한다. 0은 흰색, 1은 빨간색, 2는 파란색이다.

다음 K개의 줄에 말의 정보가 1번 말부터 순서대로 주어진다. 말의 정보는 세 개의 정수로 이루어져 있고, 순서대로 행, 열의 번호, 이동 방향이다. 행과 열의 번호는 1부터 시작하고, 이동 방향은 4보다 작거나 같은 자연수이고 1부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다.

같은 칸에 말이 두 개 이상 있는 경우는 입력으로 주어지지 않는다.

출력

게임이 종료되는 턴의 번호를 출력한다. 그 값이 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력한다.

이러한 문제를 해결할 때 문제가 되는 부분중 하나는

문제에서는 말의 위치를 표시할 때 index가 1부터 시작하고

우리가 array에서 말의 위치를 찾을때는 index가 0부터 시작하는데

어떻게 문제를 해결할 지 기준점을 잡아놓지 않는다면, 나중에 가서 혼란이 오는 경우가 많습니다.

여기서는 무조건 index를 0을 기준으로 하고 문제를 풀기 시작하겠습니다.

타일의 개수

말의 개수

일단 입력값을 저장하기 위해 총 세가지 종류의 배열과 리스트를 사용하였습니다.

int[][] tile_info = new int[n][n];
List<Integer>[][] horse_current_position = new ArrayList[n][n];
List<Horse> horses = new ArrayList<>();

각각의 배열과 리스트를 왜 만들었는지 살펴보도록 합시다.

말이 이동할 다음 위치에 존재하는 타일 색상에 따라 많은 조건이 변하고 있습니다.

다음 위치에 존재하는 타일 색상을 알기 위해서 타일 타일 색상 정보를 저장하는 배열이 하나 필요합니다.

타일의 색상 정보를 저장하는 배열은 이차원 배열로, 아래와 같이 타일의 개수 x 타일의 개수 만큼 초기화를 해줍니다.

int[][] tile_info = new int[n][n];

현재 움직이는 말은, 자기 자신보다 위에 쌓여있는 말과 같이 움직여야 하는 특성이 있습니다.

현재 타일의 위치에서 어떻게 쌓여있는지 stack 정보를 알고 싶습니다.

이차원 배열안 (타일의 모양) 안에

list를 (말의 stack이 어떻게 쌓여있는지 표시해줄 list) 넣어줍시다.

List<Integer>[][] horse_current_position = new ArrayList[n][n];

0번째, 1번째, 2번째 말들이 어디에 있는지를 확인하기 위해서는 전체 타일을 하나 하나 살펴봐야합니다.

그러기에는 너무 비효율적이지 않나요?

말들의 위치 정보와 (row, column) 이동방향 (arrow)를 저장하는 리스트를 만들어 줍시다.

List<Horse> horses = new ArrayList<>();

자 준비는 끝났습니다.

이제 문제의 정보를 우리가 만들어 놓은 배열과 리스트에 저장해 주도록 합시다.

첫번째로 문제에서 전달해주고 있는 타일의 정보를 tile_info라는 배열에 저장해 줍시다.

저장해 주면서 horse_current_position 에도 list를 같이 초기화 해 줍시다.

for (int i = 0; i < n; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 0; j < n; j++) {
        tile_info[i][j] = Integer.parseInt(st.nextToken());
        horse_current_position[i][j] = new ArrayList<>();
    }
}

다음은 말의 위치를 문제에서 제시해 주고 있습니다.

우리는 index 0을 기준으로 하고 있고, 문제에서는 index 1을 기준으로 하고 있기 때문에 row, column, arrow 정보를 문제에서 받고 -1을 빼주도록 합시다.

for (int i = 0; i <k; i++) {
    st = new StringTokenizer(br.readLine());
    int row = Integer.parseInt(st.nextToken()) - 1;
    int col = Integer.parseInt(st.nextToken()) - 1;
    int arrow = Integer.parseInt(st.nextToken()) - 1;
    Horse horse = new Horse(row, col, arrow);
    horses.add(horse);
    horse_current_position[row][col].add(i);
}

아차 Horse라는 객체에 대해서 설명을 안해드렸군요

horse라는 객체는 row, col, arrow 변수를 들고 있으면서, getter와 setter를 통해 값을 읽고, 변경할 수 있습니다.

static class Horse {
    private int row = 0;
    private int col = 0;
    private int arrow = 0;

    public Horse(int row, int col, int arrow) {
        this.row = row;
        this.col = col;
        this.arrow = arrow;
    }

    public int getRow() {
        return row;
    }

    public void setRow(int row) {
        this.row = row;
    }

    public int getCol() {
        return col;
    }

    public void setCol(int col) {
        this.col = col;
    }

    public int getArrow() {
        return arrow;
    }

    public void setArrow(int arrow) {
        this.arrow = arrow;
    }
}

또 설명을 안 드린 부분이 있습니다.

다음 위치를 이동할 때 도움을 주는 배열들입니다.

arrow의 정보가 0일때는 우

arrow의 정보가 1일때는 좌

arrow의 정보가 2일때는 상

arrow의 정보가 3일때는 하

로 이동한다는 문제를 해결하기 위한 방법입니다.

// 우, 좌, 상, 하
private static int[] add_next_row = {0, 0, -1, 1};
private static int[] add_next_col = {1, -1, 0, 0};

그리고 파란색 타일이나, 벽을 만났을 때는 방향을 바꿔야겠죠??

그때 사용하는 것이 convert_arrow 배열입니다.

현재 방향이 0이면 convert_arrow[0] 을 이용해서 -> 다음 방향을 1로 바꾸는 역할을 해주고 있습니다.

private static int[] convert_arrow = {1, 0, 3, 2};

이제 본격적으로 문제를 풀어볼 차례입니다.

턴이 1000번 이상이면 종료를 해야되기 때문에 아래와 같이 setting을 하고 진행하도록 합시다.

int turn = 0;

while (turn < 1000) {

    turn ++;
}

말이 번호 순서대로 이동을 하기 떄문에 말의 개수만큼 for loop를 돌려주도록 합시다.

현재 말의 위치를 뽑고, 이동 방향 (current_arrow)을 이용해서 다음갈 말의 위치를 next_row, next_col 의 변수를 초기화 해 줍시다.

for (int i = 0; i < k; i++) {
    Horse horse = horses.get(i);
    int current_row = horse.getRow();
    int current_col = horse.getCol();
    int current_arrow = horse.getArrow();
    int next_row = current_row + add_next_row[current_arrow];
    int next_col = current_col + add_next_col[current_arrow];
    }

다음 가야할 위치가 벽이나 파란색일 경우를 구현해 줍시다.

벽이나 파란색 타일을 만났을 경우에는 방향을 바꾸고, 현재 위치에서 바뀐 방향으로 한칸 이동하면 됩니다.

그리고 한가지 조건이 더 있습니다.

바뀐 방향이 또 벽이거나 파란색 타일인 경우입니다.

이 경우에는 현재 위치를 고수하고, 이동 방향만 변경하면 된다는 조건입니다.

if (next_row < 0 || next_col < 0 || next_row >= n || next_col >= n
    || tile_info[next_row][next_col] == 2) {
    // 방향 전환
    current_arrow = convert_arrow[current_arrow];
    horse.setArrow(current_arrow);

    next_row = current_row + add_next_row[current_arrow];
    next_col = current_col + add_next_col[current_arrow];

    if (next_row < 0 || next_col < 0 || next_row >= n || next_col >= n
        || tile_info[next_row][next_col] == 2) {
        continue;
    }
}

이동할 타일이 흰색인 경우입니다.

아래 코드를 이용해서 현재 타일에 존재하는 말들의 stack 상황을 확인해 봅니다.

List<Integer> current_tile_horses = horse_current_position[current_row][current_col];

이중에서 이동해야 하는 말 위에 존재하는 말들은 모두 이동해야 합니다.

현재 타일에는 이동해야 하는 말들을 제외하고, 이동해야 하는 말들은 moving_horses라는 리스트에 넣어둡시다.

List<Integer> current_tile_horses = horse_current_position[current_row][current_col];
List<Integer> moving_horses = new ArrayList<>();
for (int j = 0; j < current_tile_horses.size(); j++) {
    if (i == current_tile_horses.get(j)) {
        moving_horses = current_tile_horses
            .subList(j, current_tile_horses.size());
        // 현재위치에서 제거

        horse_current_position[current_row][current_col] = new ArrayList<>(current_tile_horses
            .subList(0, j));
        break;
    }
}

다음 만나는 타일이 빨간색일 경우에는 moving_horses 를 반대로 뒤집어줍니다.

// 빨간 타일이면
if (tile_info[next_row][next_col] == 1) {
    Collections.reverse(moving_horses);
}

자 거의 마지막 부분입니다.

moving_horses에 있는 말들의 위치 정보를 모두 이동할 위치로 변경해줍니다.

for (Integer moving_horse_index : moving_horses) {
    horses.get(moving_horse_index).setRow(next_row);
    horses.get(moving_horse_index).setCol(next_col);
    horse_current_position[next_row][next_col].add(moving_horse_index);
}

자 이제 다음 위치에 존재하는 말들의 개수가 4개 이상이면 종료한다는 조건을 만들어줍니다.

if (horse_current_position[next_row][next_col].size() >= 4) {
    isEnd = true;
}

while문 바로 밑에 종료조건을 만족하는 경우 while문을 벗어나라는 코드입니다.

if (isEnd) {
    break;
}

전체 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class b17837 {
    // 우, 좌, 상, 하
    private static int[] add_next_row = {0, 0, -1, 1};
    private static int[] add_next_col = {1, -1, 0, 0};
    private static int[] convert_arrow = {1, 0, 3, 2};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 체스판의 크기
        int n = Integer.parseInt(st.nextToken());
        // 말의 개수
        int k = Integer.parseInt(st.nextToken());

        int[][] tile_info = new int[n][n];
        List<Integer>[][] horse_current_position = new ArrayList[n][n];
        List<Horse> horses = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                tile_info[i][j] = Integer.parseInt(st.nextToken());
                horse_current_position[i][j] = new ArrayList<>();
            }
        }


        for (int i = 0; i <k; i++) {
            st = new StringTokenizer(br.readLine());
            int row = Integer.parseInt(st.nextToken()) - 1;
            int col = Integer.parseInt(st.nextToken()) - 1;
            int arrow = Integer.parseInt(st.nextToken()) - 1;
            Horse horse = new Horse(row, col, arrow);
            horses.add(horse);
            horse_current_position[row][col].add(i);
        }

        int turn = 0;
        boolean isEnd = false;

        while (turn < 1000) {
            if (isEnd) {
                break;
            }
            // 말의 순서대로 확인
            for (int i = 0; i < k; i++) {
                Horse horse = horses.get(i);
                int current_row = horse.getRow();
                int current_col = horse.getCol();
                int current_arrow = horse.getArrow();
                int next_row = current_row + add_next_row[current_arrow];
                int next_col = current_col + add_next_col[current_arrow];
                if (next_row < 0 || next_col < 0 || next_row >= n || next_col >= n
                    || tile_info[next_row][next_col] == 2) {
                    // 방향 전환
                    current_arrow = convert_arrow[current_arrow];
                    horse.setArrow(current_arrow);

                    next_row = current_row + add_next_row[current_arrow];
                    next_col = current_col + add_next_col[current_arrow];

                    if (next_row < 0 || next_col < 0 || next_row >= n || next_col >= n
                        || tile_info[next_row][next_col] == 2) {
                        continue;
                    }
                }

                // 스택 정리
                List<Integer> current_tile_horses = horse_current_position[current_row][current_col];
                List<Integer> moving_horses = new ArrayList<>();
                for (int j = 0; j < current_tile_horses.size(); j++) {
                    if (i == current_tile_horses.get(j)) {
                        moving_horses = current_tile_horses
                            .subList(j, current_tile_horses.size());
                        // 현재위치에서 제거

                        horse_current_position[current_row][current_col] = new ArrayList<>(current_tile_horses
                            .subList(0, j));
                        break;
                    }
                }

                // 빨간 타일이면
                if (tile_info[next_row][next_col] == 1) {
                    Collections.reverse(moving_horses);
                }

                // 위치를 옮기는 말들 위치 변경

                for (Integer moving_horse_index : moving_horses) {
                    horses.get(moving_horse_index).setRow(next_row);
                    horses.get(moving_horse_index).setCol(next_col);
                    horse_current_position[next_row][next_col].add(moving_horse_index);
                }

                if (horse_current_position[next_row][next_col].size() >= 4) {
                    isEnd = true;
                }
            }

            turn ++;
        }

        if (turn == 1000) {
            System.out.println(-1);
        } else {
            System.out.println(turn);
        }

    }

    static class Horse {
        private int row = 0;
        private int col = 0;
        private int arrow = 0;

        public Horse(int row, int col, int arrow) {
            this.row = row;
            this.col = col;
            this.arrow = arrow;
        }

        public int getRow() {
            return row;
        }

        public void setRow(int row) {
            this.row = row;
        }

        public int getCol() {
            return col;
        }

        public void setCol(int col) {
            this.col = col;
        }

        public int getArrow() {
            return arrow;
        }

        public void setArrow(int arrow) {
            this.arrow = arrow;
        }
    }
}

기억노트

[삼성 SW 역량 테스트] 새로운 게임 2

새로운 게임 2

입력

출력

티스토리툴바