[백준]8972: 미친 아두이노(java)

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

8972번: 미친 아두이노

문제

요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. 하지만, 미친 아두이노의 움직임은 예측할 수 있다.

게임은 R×C크기의 보드 위에서 이루어지며, 아래와 같은 5가지 과정이 반복된다.

1. 먼저, 종수가 아두이노를 8가지 방향(수직,수평,대각선)으로 이동시키거나, 그 위치에 그대로 놔둔다.
2. 종수의 아두이노가 미친 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되며, 종수는 게임을 지게 된다.
3. 미친 아두이노는 8가지 방향 중에서 종수의 아두이노와 가장 가까워 지는 방향으로 한 칸 이동한다. 즉, 종수의 위치를 (r1,s1), 미친 아두이노의 위치를 (r2, s2)라고 했을 때, |r1-r2| + |s1-s2|가 가장 작아지는 방향으로 이동한다.
4. 미친 아두이노가 종수의 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되고, 종수는 게임을 지게 된다.
5. 2개 또는 그 이상의 미친 아두이노가 같은 칸에 있는 경우에는 큰 폭발이 일어나고, 그 칸에 있는 아두이노는 모두 파괴된다.

종수의 시작 위치, 미친 아두이노의 위치, 종수가 움직이려고 하는 방향이 주어진다. 입력으로 주어진 방향대로 종수가 움직였을 때, 보드의 상태를 구하는 프로그램을 작성하시오. 중간에 게임에서 지게된 경우에는 몇 번째 움직임에서 죽는지를 구한다.

입력

첫째 줄에 보드의 크기 R과 C가 주어진다. (1 ≤ R, C ≤ 100)

다음 R개 줄에는 C개의 문자가 주어지며, 보드의 상태이다. '.'는 빈 칸, 'R'은 미친 아두이노, 'I'는 종수의 위치를 나타낸다.

마지막 줄에는 길이가 100을 넘지않는 문자열이 주어지며, 종수가 움직이려고 하는 방향이다. 5는 그 자리에 그대로 있는 것을 나타내고, 나머지는 아래와 같은 방향을 나타낸다.

보드를 벗어나는 입력은 주어지지 않는다.

출력

중간에 게임이 끝나는 경우에는 "kraj X"를 출력한다. X는 종수가 게임이 끝나기 전 까지 이동한 횟수이다. 그 외의 경우에는 보드의 상태를 입력과 같은 형식으로 출력한다.

예제 입력 1 

4 5
I....
.....
.R.R.
.....
6

예제 출력 1 

.I...
.RR..
.....
.....

---

풀이

시뮬레이션 문제였다.

흐름은 아래와 같다.

1. 종수가 이동한다.

2. 종수가 이동한 곳에 미친 아두이노가있는가?

3. 미친 아두이노들을 이동한다.

4. 이동후의 아두이노들이 종수와 겹치는가?

 

를 순서대로 잘 풀이해주면 된다.

1. 종수가 이동한다.

의 로직은 매우 간단하다.

for(int i=0; i<moving.length(); i++) {
    cnt++;
    int d = moving.charAt(i)-'0';
    int nx = jongsuArduino.x + dist[d][0];
    int ny = jongsuArduino.y + dist[d][1];
    jongsuArduino = new Point(nx, ny);

    if(map[nx][ny] == 'R') {
        return false;
    }
    moveCrazyArduino();
    if(map[nx][ny] == 'R') {
        return false;
    }

}

 단순히 입력받은 move 순서대로 종수를 움직여준다.

종수는 전역 클래스형 변수로 선언하였다.

 

2. 종수가 이동한 곳에 미친 아두이노가 있는가?

있다면 우리는 즉시 종료된다.

if(map[nx][ny] == 'R') {
    return false;
}

 

3. 미친 아두이노의 이동

3-1) 아두이노들 이동하기

for(int i=0; i<N; i++) {
    for(int j=0; j<M; j++) {
        if(map[i][j] == '.') continue;
        map[i][j] = '.';
        int min = Integer.MAX_VALUE;
        int nx = 0;
        int ny = 0;

        for(int d=1; d<=9; d++) {
            if(!isIn(i+dist[d][0], j+dist[d][1])) continue;
            int len = getDist(i + dist[d][0], j + dist[d][1]);
            if(min > len) {
                min = len;
                nx = i + dist[d][0];
                ny = j + dist[d][1];
            }
        }
        if(isMove[nx][ny]) {
            isDestroyed[nx][ny] = true;
        }
        isMove[nx][ny] = true;
    }
}

아두이노를 이동시킨다.

아두이노는 바깥으로 나갈 수 없으므로 바깥으로 나간 경우는 continue 해준다.

아두이노는 모든 방향으로부터의 최소거리를 구한다.

public static int getDist(int x, int y) {
    return Math.abs(x - jongsuArduino.x) + Math.abs(y - jongsuArduino.y);
}

그 최소거리로 아두이노를 이동시킨다.

isMove = true를 줌으로써 그 좌표에 이미 이동했음을 알린다.

isMove가  true인데 이동하려고 하면 isDestroyed에 true를 줌으로써 폭발해야하는 자리임을 알린다.

3-2) 겹치는 아두이노 폭발

if(isDestroyed[jongsuArduino.x][jongsuArduino.y]) {
    System.out.printf("kraj %d", cnt);
    System.exit(0);
}

for(int i=0; i<N; i++) {
    for(int j=0; j<M; j++) {
        if(isDestroyed[i][j]) {
            map[i][j] = '.';
        }
        else if(isMove[i][j]) map[i][j] = 'R';
    }
}

만약 폭발하려는 아두이노 자리에 종수가 존재한다면 시뮬레이션은 종료되야한다.

 

완탐을 돌며 만약 파괴가 true라면 .을 그게 아니고 move가 true라면 R을 map에 입력해준다.

 

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class BJ_G4_8972_미친아두이노 {
    static class Point{
        int x;
        int y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int N, M;
    static char[][] map;
    static Point jongsuArduino;
    static int cnt=0;
    static int[][] dist = {{}, {1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 0}, {0, 1}, {-1, -1}, {-1, 0}, {-1, 1}};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new char[N][M];
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = str.charAt(j);
                if(map[i][j] == 'R') {
                } else if(map[i][j] == 'I') {
                    map[i][j] = '.';
                    jongsuArduino = new Point(i, j);
                }
            }
        }
        String moving = br.readLine();

        if(goSimulate(moving)) {
            StringBuilder ans = new StringBuilder();
            map[jongsuArduino.x][jongsuArduino.y] = 'I';
            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    ans.append(map[i][j]);
                }
                if(i!=N-1) ans.append("\n");
            }
            System.out.printf("%s", ans.toString());
        } else {
            System.out.printf("kraj %d", cnt);
        }
    }

    public static boolean goSimulate(String moving) {

        for(int i=0; i<moving.length(); i++) {
            cnt++;
            int d = moving.charAt(i)-'0';
            int nx = jongsuArduino.x + dist[d][0];
            int ny = jongsuArduino.y + dist[d][1];
            jongsuArduino = new Point(nx, ny);

            if(map[nx][ny] == 'R') {
                return false;
            }
            moveCrazyArduino();
            if(map[nx][ny] == 'R') {
                return false;
            }

        }
        return true;
    }

    public static void moveCrazyArduino() {
        boolean[][] isDestroyed  = new boolean[N][M];
        boolean[][] isMove  = new boolean[N][M];

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(map[i][j] == '.') continue;
                map[i][j] = '.';
                int min = Integer.MAX_VALUE;
                int nx = 0;
                int ny = 0;

                for(int d=1; d<=9; d++) {
                    if(!isIn(i+dist[d][0], j+dist[d][1])) continue;
                    int len = getDist(i + dist[d][0], j + dist[d][1]);
                    if(min > len) {
                        min = len;
                        nx = i + dist[d][0];
                        ny = j + dist[d][1];
                    }
                }
                if(isMove[nx][ny]) {
                    isDestroyed[nx][ny] = true;
                }
                isMove[nx][ny] = true;
            }
        }

        if(isDestroyed[jongsuArduino.x][jongsuArduino.y]) {
            System.out.printf("kraj %d", cnt);
            System.exit(0);
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(isDestroyed[i][j]) {
                    map[i][j] = '.';
                }
                else if(isMove[i][j]) map[i][j] = 'R';
            }
        }
    }

    public static int getDist(int x, int y) {
        return Math.abs(x - jongsuArduino.x) + Math.abs(y - jongsuArduino.y);
    }

    public static boolean isIn(int x, int y) {
        return 0<=x && x<N && 0<=y && y<M;
    }
}