[백준 17780] 새로운 게임

문제

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

17780번: 새로운 게임

 

문제 이해

백준의 17780번 새로운 게임 문제입니다. 체스판과 말에 대한 정보가 주어지고 하나의 칸에 4개의 말이 쌓이는 턴의 번호를 출력하는 시뮬레이션 문제입니다. 삼성 SW 역량 테스트 기출문제집에 있는 새로운 게임 2 문제와 비슷한 문제풀이로 해결할 수 있습니다. 단, 가장 아래에 있는 말만 이동할 수 있다는 조건이 새로운 게임 2 문제와 다른 점입니다. 새로운 게임 2 문제에서는 이동하려는 말 위에 쌓여 있는 말의 번호를 확인해 주어야 했는데 이 문제는 이동하려는 말이 맨 아래에 있는지 판단만 해주면 되어 더 쉽게 해결할 수 있습니다.

 

풀이

 

①

먼저 체스판은 0(흰색), 1(빨간색), 2(파란색)로 구성되어 있고 각 색에 대한 정보는 문제에 예시와 함께 설명되어 있습니다. 문제의 체스판을 벗어나는 경우에는 파란색과 같다는 조건을 활용하면, 체스판을 map[N+2][N+2]의 크기로 생성하고 0과 N+1(체스판을 벗어나는 경우)는 2(파란색)를 넣어주고 나머지 (1,1)~(N,N)는 문제의 Input을 넣어줄 수 있습니다.

문제에서 주어지는 말들의 정보는 Class를 만들어 ArrayList에 저장하였습니다. 문제에서 말이 1번부터 시작하기 때문에 말의 번호를 맞춰주기 위해서 임의로 0번 말을 넣어주었고 문제풀이에서 활용하지는 않았습니다.

 

②

체스판에 올라가있는 말의 정보들을 2차원 배열의 각 칸에 Queue를 만들어 저장해서 문제를 해결할 수 있습니다. 2차원 배열 Queue를 q[N+2][N+2]로 선언하고 i번째 말의 좌표가 (x, y)라면 q[x][y]에 말의 번호인 i를 추가해주어 문제의 그림과 같이 여러 개의 말이 순서에 맞게 쌓인 형태를 구현할 수 있었습니다. 여기까지 문제의 Input을 활용한 변수 선언 및 데이터 저장을 진행하였고 이제부터 말의 이동, 게임의 종료 등의 구현을 하겠습니다.

 

③

전체적인 문제풀이 로직은 다음과 같습니다. 1000턴을 지났음에도 4개의 말이 쌓이지 않는 경우 게임을 종료하고 각 턴마다 체스판 위의 말을 번호순으로 이동시키면서 종료 조건을 충족하는지 확인합니다. 

말의 이동은 3가지 경우가 있습니다.

방향 전환 없이 이동하는 경우

방향 전환 후 이동하는 경우

방향만 전환하고 그대로 위치하는 경우

저는 말의 이동 전에 check_go 함수를 만들어 말이 어떤 이동을 할 것인지를 판단했습니다. 그 후, 방향 전환을 하는 change_dir 함수와 이동을 하는 go 함수를 만들어 위 3가지 경우에 맞는 동작을 수행하여 말을 이동시켰습니다.

 

④

이제 풀이 ②에서 만든 2차원 배열 Queue를 활용할 차례입니다. 먼저 말이 이동할 수 있는 경우를 생각해 보면 [이동하려는 말이 가장 아래에 있는 경우] 만이 존재합니다. 이동하려는 말의 좌표가 (x, y)일 때 가장 아래에 위치한 말의 번호를 bot이라 하면, bot은 Queue q[x][y]의 맨 아래에 있는 q[x][y]. peek()이라 할 수 있습니다. 이동하려는 말의 번호가 bot과 같으면 이동 가능이므로 ③의 check_go 함수를 수행하고, 다르면 이동 불가능이므로 다음 말의 번호로 넘어가게 됩니다.

check_go 함수 수행 후 말의 이동이 가능하다면, q[x][y]에 위치한 모든 말의 번호들을 임시 ArrayList에 넣어줍니다. 그 후, 이동하려는 좌표가 0(빈칸)이라면 순서를 바꾸지 않고 그대로 q[nx][ny]에 넣어주면 되고 1(빨간색)이라면 임시 ArrayList의 뒤에서부터 꺼내어 q[nx][ny]에 넣어주면 됩니다.

 

⑤

1턴부터 1000턴까지 전체 말들을 순차적으로 이동시키면서 종료 조건을 확인하면 문제를 해결할 수 있습니다.

위 문제 풀이 방법 중 다른 문제에 활용할 수 있는 것은 입력으로 주어지는 체스판의 행과 열의 크기를 각각 +2만큼 추가해주어 외벽을 설치하면 Index가 배열의 범위를 벗어나는 것을 예방할 수 있다는 점입니다. 그리고 2차원 배열 Queue를 사용하면 문제를 좀 더 쉽게 이해 및 구현할 수 있습니다. 다만 2차원 배열 Queue는 2차원 배열의 크기만큼 생성 후, 각 칸 [x][y]마다 Queue를 생성해주어야 한다는 점을 유의해 주셔야 합니다.

 

소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ_17780 {
    static int n, k, ans, nx, ny, gnum, qsize, tsize;
    static int[][] map;
    static int[] dx = { 0, 0, 0, -1, 1 }; // 1~4: 우좌상하
    static int[] dy = { 0, 1, -1, 0, 0 };
    static ArrayList<P> horse; //horse: 말의 정보
    static ArrayList<Integer> temp;
    static Queue<Integer>[][] q;
    static StringTokenizer str;
 
    public static void main(String[] args) throws Exception {
        init();
        ans = -1; //ans: 결과값
        for (int turn = 1; turn <= 1000; turn++) {
            for (int now = 1; now <= k; now++) {
                nx = horse.get(now).x; //nx, ny: 현재 말의 좌표
                ny = horse.get(now).y;
                
                if(q[nx][ny].peek() != now) continue; //이동하려는 말이 맨 아래에 있지 않은 경우, 다음 말로 넘어감.
                
                gnum = check_go(now); //gnum: 말의 이동 방법을 미리 확인
                            
                if (gnum == 2) { //gnum 2: 방향만 바뀌는 경우
                    change_dir(now); //change_dir: 현재 말의 방향만 바꿔줌.                
                } else { 
                    if(gnum == 1) change_dir(now); //gnum 1: 방향이 바뀌고 이동하는 경우
                    go(now); //go: gnum이 0 또는 1일 때 말의 이동
                    add(); //add: 임시 저장한 temp를 이동한 말 위에 쌓아올림.
                }
                if (q[nx][ny].size() >= 4) { //종료조건: 말이 4개 쌓이는 경우 턴 종료
                    ans = turn;
                    break;
                }
            }
            if (ans != -1) break; //종료조건을 통해 결과값 ans가 바뀐 경우 break
        }
        System.out.println(ans);
    }
 
    private static void init() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = new StringTokenizer(br.readLine().trim());
        n = Integer.parseInt(str.nextToken()); //n: 체스판의 크기
        k = Integer.parseInt(str.nextToken()); //k: 말의 개수
        map = new int[n + 2][n + 2]; //map[][]: 체스판의 정보
        q = new LinkedList[n + 2][n + 2]; //q[][]: 드론의 정보
        for (int i = 0; i <= n + 1; i++) {
            for (int j = 0; j <= n + 1; j++) {
                map[i][j] = 2; //체스판의 범위를 벗어난 경우(i 또는 j가 0 또는 n+1인 경우) 파란색(2)와 같으므로 초기값은 2
                q[i][j] = new LinkedList<>(); //2차원 배열 q는 각 칸마다 LinkedList를 생성해주어야 함.
            }
        }
        for (int i = 1; i <= n; i++) {
            str = new StringTokenizer(br.readLine().trim());
            for (int j = 1; j <= n; j++) {
                map[i][j] = Integer.parseInt(str.nextToken()); //체스판의 정보를 입력받음.
            }
        }
        horse = new ArrayList<>();
        horse.add(new P(0, 0, 0));
        for (int i = 1; i <= k; i++) {
            str = new StringTokenizer(br.readLine().trim());
            int tx = Integer.parseInt(str.nextToken());
            int ty = Integer.parseInt(str.nextToken());
            int tdir = Integer.parseInt(str.nextToken());
            horse.add(new P(tx, ty, tdir));
            q[tx][ty].add(i);
        }
    }
    
    private static int check_go(int now) { //결과값 gcnt(0: 그냥 이동, 1: 방향 전환 이동, 2: 방향만 전환)
        int tdir = horse.get(now).dir;
        int gcnt = 0;
        if (map[nx + dx[tdir]][ny + dy[tdir]] == 2) {
            gcnt++;
            if (map[nx - dx[tdir]][ny - dy[tdir]] == 2) gcnt++;
        }
        return gcnt;
    }
    
    private static void change_dir(int now) { //change_dir: 말의 이동방향을 반대로 전환
        int tdir = horse.get(now).dir;
        if (tdir == 1) horse.get(now).dir = 2;
        else if (tdir == 2) horse.get(now).dir = 1;
        else if (tdir == 3) horse.get(now).dir = 4;
        else horse.get(now).dir = 3;
    }
    
    private static void go(int cur) { //go: 말의 이동
        temp = new ArrayList<>(); //temp: 말 번호 임시 저장 장소
        qsize = q[nx][ny].size(); //qsize: 현재 좌표에서의 말 개수
        for (int s = 0; s < qsize; s++) {
            temp.add(q[nx][ny].poll()); //이동하려는 말의 현재 좌표에 있는 말들을 임시 ArrayList에 저장
        }        
        //말의 좌표 이동
        nx = horse.get(cur).x = horse.get(cur).x + dx[horse.get(cur).dir];
        ny = horse.get(cur).y = horse.get(cur).y + dy[horse.get(cur).dir];
    }
    
    private static void add() { //add: 임시 저장한 말 번호들을 2차원 배열 Queue에 추가
        tsize = temp.size(); //tsize: 임시 ArrayList에 들어있는 말의 개수
        if (map[nx][ny] == 0) { //이동하려는 위치가 0(빈 칸)인 경우
            for (int s = 0; s < tsize; s++) {
                q[nx][ny].add(temp.get(s));
                horse.get(temp.get(s)).x = nx;
                horse.get(temp.get(s)).y = ny;
            }
        } else { //이동하려는 위치가 1(빨간색)인 경우
            for (int s = tsize - 1; s >= 0; s--) {
                q[nx][ny].add(temp.get(s));
                horse.get(temp.get(s)).x = nx;
                horse.get(temp.get(s)).y = ny;
            }
        }
    }
 
    static class P { //P: 말의 정보를 저장하기 위한 Class
        int x, y, dir;
        public P() {}
        public P(int x, int y, int dir) {
            this.x = x;
            this.y = y;
            this.dir = dir;
        }
    }
}