[ 백준 17837 ] 새로운 게임 2 (java)

[ 백준 17837 ] 새로운 게임 2 (자바)

 

 

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

17837번: 새로운 게임 2

 

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다. 턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다.  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번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다. 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

 

 

핵심

• 문제 이해 
• 시간 복잡도: 지도 상에 말들은 끝에 위치한 말부터 이동 ( stack,. 등 )
• 답 찾으면 종료
• 말이 위치한 맵에 말 객체가 아닌 말 번호를 저장하여 계산 시간 감소 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요

 

 

주석 참고 

 

 
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static int N, K;
    static int[][] map;
    static ArrayList<Integer>[][] horsemap;
    static horse[] horses;
    static class horse{
        int y, x, dir;
        horse(int y, int x, int dir){
            this.y = y;
            this.x = x;
            this.dir = dir;
        }
    }
    static int[][] delta = {
            {0, 1},
            {0, -1},
            {-1, 0},
            {1, 0}
    };
    
    static int[] change = {1,0,3,2}; // 방향 전환 배열, ex 0이 들어오면 1로 방향이 바뀐다. 
    static boolean isRange(int y, int x) {
        return y >= 0 && y<N && x >=0 && x <N;
    }
    
    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];             // 보드 색상 
        horsemap = new ArrayList[N][N]; // 보드 위에 쌓인 말들의 번호  
        horses = new horse[K+1];             // 1번 ~ K번 말타입 배열 
        
        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());
                horsemap[i][j] = new ArrayList<Integer>();
            }
        }
        
        int iy, ix, idir;
        for(int i = 1 ; i <= K ; i++) {
            st = new StringTokenizer(br.readLine());
            iy = Integer.parseInt(st.nextToken())-1;
            ix = Integer.parseInt(st.nextToken())-1;
            idir = Integer.parseInt(st.nextToken())-1;
            horses[i] = new horse(iy, ix, idir);
            horsemap[iy][ix].add(i);
        }
        int turn = 1, ny, nx, dir, rm;
        horse cur;
        ArrayList<Integer> templist = new ArrayList<Integer>();
        
        for(; turn <= 1000 ;turn++) {
            for(int h = 1 ; h <= K ; h++) {
                cur = horses[h];
                dir = cur.dir;
                ny = cur.y + delta[dir][0];
                nx = cur.x + delta[dir][1];
                
                if( !isRange(ny, nx) || map[ny][nx] == 2) { // 다음이 보드 밖 또는 파란 칸 
                    // 범위 바꾸고 다음칸 새로 설정
                    dir = change[dir];
                    horses[h].dir = dir;
                    ny = horses[h].y + delta[dir][0];
                    nx = horses[h].x + delta[dir][1];
                    
                }
                
                if(isRange(ny, nx) && map[ny][nx] != 2) { // 다음이 보드 안이고 파란 칸 아닐때 
                    if(map[ny][nx] == 0) { // 다음이 흰색 
                        // top부터 h까지 제거하고 templist에 추가 
                        rm = horsemap[cur.y][cur.x].remove(horsemap[cur.y][cur.x].size()-1);
                        while(rm != h) {
                            templist.add( rm );
                            rm =   horsemap[cur.y][cur.x].remove(horsemap[cur.y][cur.x].size()-1);
                        }
                        templist.add(rm);
                        
                        while(!templist.isEmpty()) {
                            rm= templist.remove(templist.size()-1);
                            // 말 위치 변경 
                            horses[rm].y = ny;
                            horses[rm].x = nx;
                            // 지도에 말 쌓기 
                            horsemap[ny][nx].add(rm);
                        }
                    }else { // 다음이 빨강
                        
                        rm = horsemap[cur.y][cur.x].remove(horsemap[cur.y][cur.x].size()-1);
                        while(rm != h) {
                            horses[rm].y = ny;
                            horses[rm].x = nx;
                            horsemap[ny][nx].add( rm );
                            rm =   horsemap[cur.y][cur.x].remove(horsemap[cur.y][cur.x].size()-1);
                        }
                        horses[rm].y = ny;
                        horses[rm].x = nx;
                        horsemap[ny][nx].add(rm);
                    }
                    
                    // 말이 이동하게 되면 (ny, nx)만 길이가 변하므로 (ny, nx)만 검사 후 바로 종료 
                    if(horsemap[ny][nx].size() >= 4) {
                        System.out.println(turn);
                        return;
                    }
                }
            }
        }
        
        // 1000 넘김 
        System.out.println(-1);
    }
}