[백준 17837] 새로운 게임2

문제

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

17837번: 새로운 게임 2

 

문제 이해

백준의 삼성 SW 역량 테스트 기출문제집에 있는 새로운 게임 2 문제입니다. 체스판과 말에 대한 정보가 주어지고 하나의 칸에 4개의 말이 쌓이는 턴의 번호를 출력하는 시뮬레이션 문제입니다. 시뮬레이션 문제들은 문제의 조건을 잘못 이해하거나 빼먹은 경우 디버깅하면서 해결하는 데 시간이 많이 소요되기 때문에 문제를 충분히 읽고 고민하는 시간이 필요합니다. 저는 시뮬레이션 문제를 풀 때, 연습장에 문제의 조건들을 정리하고 어떻게 구현할지 생각해본 후 코딩을 시작하는 편입니다.

 

풀이

 

①

먼저 체스판은 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를 활용할 차례입니다. 문제에 나와있는 그림 예제의 첫 번째 턴에서 3번 말을 이동시켜보겠습니다. 3번 말은 풀이 ③에서 말한 이동 중 방향 전환 없이 이동하는 경우입니다. 이동을 위해서 3번 말을 포함해서 3번 말 위에 쌓여 있는 말들의 번호를 임시 ArrayList에 3, 1, 2 순으로 저장합니다. 이동하려는 체스판 위치의 정보가 1(빨간색)이기 때문에 임시 ArrayList의 뒤에서부터 꺼내어 2, 1, 3 순으로 q[x][y]에 넣어주면 됩니다. 만약, 이동하려는 체스판 위치의 정보가 0(빈칸)이라면 순서를 바꾸지 않고 ArrayList에 저장한 순서인 3, 1, 2 그대로 q[x][y]에 넣어주면 됩니다.

2차원 배열 Queue를 사용하는 이유는 바로 3번 말 위에 쌓여져 있는 말들의 번호와 순서를 활용할 수 있기 때문입니다. 3번 말의 현재 위치가 (x, y)라면 q[x][y]에서 하나씩 꺼내면서 3번 말인지 확인하고 아니라면 그대로 다시 넣어주고 3번 말이라면 그때부터 마지막까지 임시 ArrayList에 넣어 활용할 수 있습니다.

 

⑤

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

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

 

소스 코드

package algo;
 
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 Main {
    static int n, k, ans, nx, ny, gnum, qsize;
    static boolean find;
    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;
                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: 말 번호 임시 저장 장소
        find = false; //find: 현재 말 위에 쌓여져 있는 말들만 이동하기 위해 확인하는 변수
        qsize = q[nx][ny].size(); //qsize: 현재 좌표에서의 말 개수
        for (int s = 0; s < qsize; s++) {
            int a = q[nx][ny].poll();
            if (a == cur) find = true; //현재 말을 발견한 경우 find = true
            if (find) temp.add(a); //현재 말부터 위에 쌓인 말들은 temp에 넣어줌.
            else q[nx][ny].add(a); //그렇지 않은 말들은 그대로 다시 넣어줌.
        }        
        //말의 좌표 이동
        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에 추가
        if (map[nx][ny] == 0) { //이동하려는 위치가 0(빈 칸)인 경우
            for (int s = 0; s < temp.size(); 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 = temp.size() - 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;
        }
    }
}