[백준 8972] 미친 아두이노 - JAVA

문제 링크 : https://www.acmicpc.net/problem/8972

문제 정의

해당 문제의 로직은 다음과 같습니다.

1. 종수가 조종하는 아두이노를 명령에 따라 이동
   1-1. 미친 아두이노와 충돌 시 "Kraj X"를 출력 (X는 이동 횟수) 후 종료
   1-2. 미친 아두이노와 충돌 안할 시 명령된 방향으로 아두이노 이동
2. 미친 아두이노 동시 이동
   2-1. 종수가 조종하는 아두이노와 충돌 시 "Kraj X"를 출력 (X는 이동 횟수) 후 종료
   2-2. 종수가 조종하는 아두이노와 충돌 안할 시 미친 아두이노 이동
   2-3. 미친 아두이노끼리 충돌 시 소멸
3. 1로 돌아가 다음 명령 수행

---

접근 방법

위의 로직대로 코드를 작성합니다.

1. 우선 moveArduino라는 메서드로 종수가 조종하는 아두이노를 이동합니다.
   1-1. moveArduino가 false인 경우 Kraj X를 출력 (X는 이동 횟수) 후 종료
   1-2. moveArduino를 움직일 수 있는 경우 이동 후 true

2. 다음은 미친 아두이노를 이동하기 위해 moveCrazyArduino 메서드를 수행합니다.
   2-1. moveCrazyArduino가 false인 경우 Kraj X를 출력 (X는 이동 횟수) 후 종료
   2-2. true인 경우 미친 아두이노 충돌 여부에 따라 소멸 혹은 미친 아두이노 이동

3. 다음 명령 수행

---

moveArduino 메서드

static boolean moveArduino(int d) {
    if (d == 5) return true;

    int ny = cy + dy[d];
    int nx = cx + dx[d];
      
    if (board[ny][nx] == 'R') {
        return false;
    }

    board[ny][nx] = 'I';
    board[cy][cx] = '.';
    cy = ny;
    cx = nx;

    return true;
}

이동 방향으로 이동하는데
해당 위치에 미친 아두이노가 존재하면 false
존재하지 않으면 true를 반환합니다.

---

moveCrazyArduino 메서드

static boolean moveCrazyArduino() {
    int[][] visited = new int[R][C];

    int size = q.size();
    while (size-- > 0) {
        Arduino arduino = q.poll();
        int y = arduino.y;
        int x = arduino.x;
        board[y][x] = '.';

        int d = calMoveDir(y, x);

        int ny = y + dy[d];
        int nx = x + dx[d];
            
        if (visited[ny][nx] == 0) {
            q.offer(new Arduino(ny, nx));
            visited[ny][nx] = 1;
        }
        else {
            visited[ny][nx] = -1;
        }
    }

    size = q.size();
    while(size-- > 0) {
        Arduino arduino = q.poll();
        int y = arduino.y;
        int x = arduino.x;

        if (board[y][x] == 'I') {
            return false;
        }

        if (visited[y][x] == 1) {
            q.offer(new Arduino(y, x));
            board[y][x] = 'R';
        }
    }

    return true;
}

큐에는 미친 아두이노의 좌표값이 저장되어 있습니다.

첫 번째 큐 순회

위쪽 while문에서 순회할 때는
다음 이동 좌표로 이동하며 방문처리를 하는데
첫 아두이노가 방문할 때는 visited[ny][nx] = 1로 처리해 방문된 위치임을 표시합니다.
그런 후 후보를 추려내기 위해 다시 큐에 저장합니다.

같은 곳에 여러 미친 아두이노가 오는 경우는 visited[ny][nx] = -1로 처리해서
충돌이 일어나는 좌표임을 체크합니다.

두 번째 큐 순회

아래쪽 while문에서 순회할 때는
가장 먼저 이동한 좌표에 종수가 조종하는 아두이노가 있는지 확인하고

• 있다면 true 반환
• 없다면 아래 로직을 수행

종수가 조종하는 아두이노가 없는 경우에는
visited[y][x]를 확인해 충돌이 발생하는 좌표인지, 아닌지 판별합니다.

충돌하는 경우 아두이노가 소멸하기에 해당 좌표값을 .으로 변경
충돌하지 않는 경우 아두이노가 해당 좌표로 이동해야 하기에 board[y][x] = 'R'로 지정한 후 큐에 저장합니다.

---

calMoveDir 메서드

해당 메서드는 미친 아두이노의 최적 이동 방향을 계산합니다.

static int calMoveDir(int y, int x) {
    int vertical = 0;
    int horizontal = 0;
        
    if (y < cy) {
        vertical = 1;
    }
    else if (y > cy) {
        vertical = -1;
    }

    if (x < cx) {
        horizontal = 1;
    }
    else if (x > cx) {
        horizontal = -1;
    }

    for (int d = 1; d <= 9; d++) {
        if (vertical == dy[d] && horizontal == dx[d]) {
            return d;
        }
    }

    return 5;
}

vertical은
수직으로 추적해야할 아두이노가 나보다 위쪽인 경우 -1
수직으로 추적해야할 아두이노가 나와 같은 y좌표인 경우 0
수직으로 추적해야할 아두이노가 나보다 아래쪽인 좌표인 경우 1

horizontal은
수평으로 추적해야할 아두이노가 나보다 왼쪽인 경우 -1
수평으로 추적해야할 아두이노가 나와 같은 x좌표인 경우 0
수평으로 추적해야할 아두이노가 나보다 오른쪽인 좌표인 경우 1

계산한 이후
dy dx 배열과 비교해
몇 번 order 인지를 판별 후 반환합니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

class Arduino {
    int y;
    int x;

    public Arduino (int y, int x) {
        this.y = y;
        this.x = x;
    }
}

public class Main {
    static StringTokenizer st;
    static int R;
    static int C;
    static int cy;
    static int cx;
    static int[] dy = {0, 1, 1, 1, 0, 0, 0, -1, -1, -1};
    static int[] dx = {0, -1, 0, 1, -1, 0, 1, -1, 0, 1};
    static char[][] board;
    static ArrayDeque<Arduino> q;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        q = new ArrayDeque<>();

        board = new char[R][C];

        for (int i = 0; i < R; i++) {
            String s = br.readLine();
            for (int j = 0; j < C; j++) {
                board[i][j] = s.charAt(j);

                if (board[i][j] == 'I') {
                    cy = i;
                    cx = j;
                }

                else if (board[i][j] == 'R') {
                    q.offer(new Arduino(i, j));
                }
            }
        }

        System.out.println(getAnswer(br.readLine().toCharArray()));
    }

    static String getAnswer(char[] orders) {
        for (int i = 0; i < orders.length; i++) {
            int order = (int)orders[i] - '0';
            if (!moveArduino(order) || !moveCrazyArduino()) {
                return "kraj " + (i+1);
            }
        }

        return print(board);
    }

    static String print(char[][] board) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                sb.append(board[i][j]);
            }
            sb.append("\n");
        }

        return sb.toString();
    }

    static boolean moveCrazyArduino() {
        int[][] visited = new int[R][C];

        int size = q.size();
        while (size-- > 0) {
            Arduino arduino = q.poll();
            int y = arduino.y;
            int x = arduino.x;
            board[y][x] = '.';

            int d = calMoveDir(y, x);

            int ny = y + dy[d];
            int nx = x + dx[d];
            
            if (visited[ny][nx] == 0) {
                q.offer(new Arduino(ny, nx));
                visited[ny][nx] = 1;
            }
            else {
                visited[ny][nx] = -1;
            }
        }
        
        size = q.size();
        while(size-- > 0) {
            Arduino arduino = q.poll();
            int y = arduino.y;
            int x = arduino.x;

            if (board[y][x] == 'I') {
                return false;
            }

            if (visited[y][x] == 1) {
                q.offer(new Arduino(y, x));
                board[y][x] = 'R';
            }
        }

        return true;
    }

    static int calMoveDir(int y, int x) {
        int vertical = 0;
        int horizontal = 0;
        
        if (y < cy) {
            vertical = 1;
        }
        else if (y > cy) {
            vertical = -1;
        }

        if (x < cx) {
            horizontal = 1;
        }
        else if (x > cx) {
            horizontal = -1;
        }

        for (int d = 1; d <= 9; d++) {
            if (vertical == dy[d] && horizontal == dx[d]) {
                return d;
            }
        }

        return 5;
    }

    static boolean moveArduino(int d) {
        if (d == 5) return true;

        int ny = cy + dy[d];
        int nx = cx + dx[d];
        
        if (board[ny][nx] == 'R') {
            return false;
        }

        board[ny][nx] = 'I';
        board[cy][cx] = '.';
        cy = ny;
        cx = nx;

        return true;
    }
}