BOJ 8972: 미친 아두이노

문제 풀이

먼저 종수의 아두이노를 이동한다.
종수의 아두이노는 미친 아두이노가 있는 곳에 가면 지게된다.

미친 아두이노는 미리 mad라는 Queue에 저장해두었다가 꺼내 쓴다.
미친 아두이노들은 종수의 아두이노와의 최소 거리로 이동하므로 방향index를 순회하며 이동할 좌표를 찾는다.
미친 아두이노가 이동할 좌표에 종수의 아두이노가 있다면 종수는 게임에서 지게되므로 false를 반환한다.
미친 아두이노가 한 칸에 여러대 있을 경우에는 아두이노가 폭발해 사라지므로 이를 알기 위해 int[][] 배열을 선언하고, 각 칸에 미친 아두이노가 몇개 이동했는지를 저장한다.
아두이노가 1개보다 많을때에는 다시 mad Queue에 넣지 않는다.
미친 아두이노가 1개일때만 mad Queue에 넣는다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class ArduinoIndex {
        int i;
        int j;
        ArduinoIndex(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
    static int R, C;
    static int[][] map;
    static Queue<ArduinoIndex> mad = new LinkedList<>();
    static ArduinoIndex jongsu;
    static int[] dirI = {0, 1, 1, 1, 0, 0, 0, -1, -1, -1};
    static int[] dirJ = {0, -1, 0, 1, -1, 0, 1, -1, 0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new int[R][C];

        for(int i = 0; i < R; i++) {
            String temp = br.readLine();
            for(int j = 0; j < C; j++) {
                char t = temp.charAt(j);
                if(t == 'R') {
                    map[i][j] = -1;
                    mad.add(new ArduinoIndex(i, j));
                } else if(t == 'I') {
                    jongsu = new ArduinoIndex(i, j);
                }
            }
        }

        String order = br.readLine();
        boolean flag = true;
        for(int orderIndex = 0; orderIndex < order.length(); orderIndex++) {
            int index = order.charAt(orderIndex) - '0';
            if(!moveJongsu(index)) {
                System.out.println("kraj " + (orderIndex + 1));
                flag = false;
                break;
            }
            if(!moveArduino()) {
                System.out.println("kraj " + (orderIndex + 1));
                flag = false;
                break;
            }
        }
        if(flag) {
            char[][] map = new char[R][C];
            for(int i = 0; i < R; i++) {
                Arrays.fill(map[i], '.');
            }
            map[jongsu.i][jongsu.j] = 'I';
            while(!mad.isEmpty()) {
                ArduinoIndex temp = mad.poll();
                map[temp.i][temp.j] = 'R';
            }
            for(int i = 0; i < R; i++) {
                for(int j = 0; j < C; j++) {
                    System.out.print(map[i][j]);
                }
                System.out.println();
            }
        }
    }

    public static boolean moveJongsu(int index) {
        int nextI = jongsu.i + dirI[index];
        int nextJ = jongsu.j + dirJ[index];

        if(map[nextI][nextJ] == -1) {
            return false;
        }
        jongsu.i = nextI;
        jongsu.j = nextJ;
        return true;
    }

    public static boolean moveArduino() {
        int[][] arduinoMap = new int[R][C];
        while(!mad.isEmpty()) {
            ArduinoIndex temp = mad.poll();
            map[temp.i][temp.j] = 0;
            int minI = temp.i;
            int minJ = temp.j;
            int minDistance = Integer.MAX_VALUE;
            for(int index = 1; index < 10; index++) {
                int nextI = temp.i + dirI[index];
                int nextJ = temp.j + dirJ[index];
                if(nextI < 0 || nextI >= R || nextJ < 0 || nextJ >= C) {
                    continue;
                }
                int nextDistance = Math.abs(nextI - jongsu.i) + Math.abs(nextJ - jongsu.j);
                if(nextDistance < minDistance) {
                    minI = nextI;
                    minJ = nextJ;
                    minDistance = nextDistance;
                }
            }
            if((minI == jongsu.i) && (minJ == jongsu.j)) {
                return false;
            }
            arduinoMap[minI][minJ]++;
        }

        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(arduinoMap[i][j] == 1) {
                    mad.add(new ArduinoIndex(i, j));
                    map[i][j] = -1;
                }
            }
        }
        return true;
    }
}

백준
github