[백준 17780] 새로운 게임 - JAVA // le_effort

새로운 게임

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.5 초	512 MB	1370	557	408	39.573%

문제

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 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번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다.

  • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

다음은 크기가 4×4인 체스판 위에 말이 4개 있는 경우이다.

첫 번째 턴은 다음과 같이 진행된다.

두 번째 턴은 다음과 같이 진행된다.

체스판의 크기와 말의 위치, 이동 방향이 모두 주어졌을 때, 게임이 종료되는 턴의 번호를 구해보자.

입력

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

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

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

출력

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

제한

• 4 ≤ N ≤ 12
• 4 ≤ K ≤ 10

예제 입력 1 복사

xxxxxxxxxx
4 4
0 0 2 0
0 0 1 0
0 0 1 2
0 2 0 0
2 1 1
3 2 3
2 2 1
4 1 2

예제 출력 1 복사

xxxxxxxxxx
-1

예제 입력 2 복사

xxxxxxxxxx
4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1
1 2 1
1 3 1
1 4 1

예제 출력 2 복사

xxxxxxxxxx
1

예제 입력 3 복사

xxxxxxxxxx
4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1
1 2 1
1 3 1
2 4 3

예제 출력 3 복사

xxxxxxxxxx
1

예제 입력 4 복사

xxxxxxxxxx
4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1
1 2 1
1 3 1
3 3 3

예제 출력 4 복사

xxxxxxxxxx
2

예제 입력 5 복사

xxxxxxxxxx
4 4
0 0 2 0
0 0 1 0
0 0 1 2
0 2 0 0
2 1 1
3 2 3
2 2 1
4 1 3

예제 출력 5 복사

xxxxxxxxxx
8

예제 입력 6 복사

xxxxxxxxxx
6 10
0 1 2 0 1 1
1 2 0 1 1 0
2 1 0 1 1 0
1 0 1 1 0 2
2 0 1 2 0 1
0 2 1 0 2 1
1 1 1
2 2 2
3 3 4
4 4 1
5 5 3
6 6 2
1 6 3
6 1 2
2 4 3
4 2 1

 

 

풀이

 

각각의 조건에 맞춰서 구현을 해주면 됩니다.

 

이 때 가장 밑에 있는 말을 움직이는 것은

 

저는 2차원 어레이리스트를 만들어서

list.get(0)이 가장 아래에 있는 말이라고 정하고 했습니다.

 

주의 할 점은 파란색 칸으로 이동 할 때의 경우인데, 이동 한 칸이 파란색이라면

방향을 바꾸고나서 다음 이동칸이 파란색 or 범위를 벗어나는 경우가 아니면

 

방향을 바꾸고 이동한칸이 빨간색 or 흰색 일때 조건으로 처리를 해줘야 했습니다.

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    static int n,k;
    static int dx[] = {10000,0,0,-1,1};
    static int dy[] = {10000,1,-1,0,0};
    static int map[][];
    static ArrayList<Integer>[][] map_horse_info;
    static Horse[] horse;
    static int ans = 0;
    public static void print() {
        System.out.println("==========");
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                System.out.print(map_horse_info[i][j].size()+" ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);
        
        map = new int[n+1][n+1];
        map_horse_info = new ArrayList[n+1][n+1];
        horse = new Horse[k+1];
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                map_horse_info[i][j] = new ArrayList<>();
            }
        }
        
        for(int i=1; i<=n; i++) {
            input = br.readLine().split(" ");
            for(int j=1; j<=n; j++) {
                map[i][j] = Integer.parseInt(input[j-1]);
            }
        }
        
        
        for(int i=0; i<k; i++) {                
            input = br.readLine().split(" ");
            int x = Integer.parseInt(input[0]);
            int y = Integer.parseInt(input[1]);
            int dir = Integer.parseInt(input[2]);
            horse[i+1] = new Horse(x,y,dir);
        }
        
        
        for(int i=1; i<=k; i++) {
            Horse tmp = horse[i];
            map_horse_info[tmp.x][tmp.y].add(i);
        }
        
        
        while(true) {
            if(ans>=1000) {
                System.out.println(-1);
                return ;
            }
            if(game_over()) {
                System.out.println(ans);
                break;
            }
            for(int i=1; i<=k; i++) {
                Horse move_horse = horse[i];
​
                if(isGoPossible(move_horse.x,move_horse.y,i)) {
                    go(i,move_horse.x,move_horse.y);
                }
            }
            ans++;
        }
    }
    
    public static boolean game_over() {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(map_horse_info[i][j].size()>=4) {
                    return true;
                }
            }
        }
        return false;
    }
    
    
    
    
    
    
    public static void go(int num, int map_x, int map_y) {
        
        Horse go_horse = horse[num];
        
        
        int nx = go_horse.x+dx[go_horse.dir];
        int ny = go_horse.y+dy[go_horse.dir];
        
        if(!isRange(nx,ny) || map[nx][ny]==2) {
            
            // 1. 일단 방향을 바꾼다
            horse[num].dir = dir_change(go_horse.dir);
            go_horse.dir = horse[num].dir;
            
            // 2. 방향 바꾸고 새로 이동한 칸이 범위를 벗어나거나 블루 칸 인경우
            int blue_x = go_horse.x+dx[go_horse.dir];
            int blue_y = go_horse.y+dy[go_horse.dir];
            
            if(!isRange(blue_x,blue_y) || map[blue_x][blue_y]==2) {
                return ;
            }
            
            // 3. 방향 바꾸고 새로 이동한 칸이 블루 칸이 아닌경우
            if(map[blue_x][blue_y]==0) {
                white(blue_x,blue_y,map_x,map_y);
            }
            else {
                red(blue_x,blue_y,map_x,map_y);
            }
            
        }
        
        else if(map[nx][ny] ==0) {
            white(nx,ny,map_x,map_y);
        }
        
        
        else if(map[nx][ny]==1) {
            red(nx,ny,map_x,map_y);
        }
        
    }
    public static void blue(int nx, int ny, int map_x, int map_y) {
        int size = map_horse_info[map_x][map_y].size();
        
        
        for(int i=0; i<size; i++) {
            int horse_num = map_horse_info[map_x][map_y].remove(0);
            map_horse_info[nx][ny].add(horse_num);
            horse[horse_num].x = nx;
            horse[horse_num].y= ny;
            
        }
    }
    
    
    public static void red(int nx, int ny, int map_x, int map_y) {
        ArrayList<Integer>tmp = new ArrayList<>();
        int size = map_horse_info[map_x][map_y].size()-1;
        for(int i=size; i>=0; i--) {
            int horse_num = map_horse_info[map_x][map_y].remove(i);
            tmp.add(horse_num);
        }
        
        
        for(int i=0; i<tmp.size(); i++) {
            int horse_num = tmp.get(i);
            horse[horse_num].x = nx;
            horse[horse_num].y= ny;
            map_horse_info[nx][ny].add(horse_num);
        }
        
        
    }
    public static void white(int nx, int ny, int map_x, int map_y) {    
        int size = map_horse_info[map_x][map_y].size();
        
        
        for(int i=0; i<size; i++) {
            int horse_num = map_horse_info[map_x][map_y].remove(0);
            map_horse_info[nx][ny].add(horse_num);
            horse[horse_num].x = nx;
            horse[horse_num].y= ny;
        }
    }
    public static boolean isRange(int x, int y) {
        if(x>=1 && y>=1 && x<=n && y<=n) {
            return true;
        }
        return false;
    }
    public static int dir_change(int dir) {
        if(dir ==1) {
            return 2;
        }
        if(dir==2) {
            return 1;
        }
        if(dir==3) {
            return 4;
        }
        if(dir==4) {
            return 3;
        }
        return 10000;
    }
    public static boolean isGoPossible(int x, int y, int num) {
        if(map_horse_info[x][y].get(0) == num) {
            return true;
        }
        return false;
    }
}
class Horse{
    int x,y,dir;
    Horse(int x ,int y, int dir){
        this.x=x;
        this.y=y;
        this.dir= dir;
    }
}
​