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

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

8972번: 미친 아두이노

풀이

🪑 구현 + 탐색 문제였다! 구현 문제 특징은 문제는 어렵지 않으나 구현하는 과정에서 놓칠 수 있는 조건들이 발생하기 쉽고, 문제의 조건에 맞게 구현하되 시간초과가 발생하지 않도록 구현해 주어야 한다.

 

구현 문제를 풀 때에는 조건을 꼼꼼히! 확인해 주어야 나중에 고생을 덜한다.

 

📝 문제의 조건을 꼼꼼히! 확인해 보자.

• 종수의 아두이노를 먼저 이동시킨다. 가만히 있는 경우를 포함해 9가지 경우의 이동 범위를 갖는다.
• 종수의 아두이노가 이동 중에 미친 아두이노를 만나게 되면 게임은 끝난다.
• 종수의 아두이노를 이동 시킨 다음 미친 아두이노를 이동시킨다. 미친 아두이노는 가만히 있을 수 없으므로 8가지 경우의 이동 범위를 갖는다.
• 모든 미친 아두이노의 이동이 끝난 후 한 공간에 2개 이상의 미친 아두이노가 있다면 폭발하여 사라진다.
• 미친 아두이노가 종수의 아두이노를 만나게 되면 게임은 끝난다.

 

 

🔧 문제를 풀어 보자!

- 문제 풀이 순서는 문제의 조건에 나온 순서와 동일하다. 조건을 따라가며 구현해 보자!

 

🔹 종수의 아두이노를 먼저 이동시킨다.

- 종수의 아두이노는 바로 이동시키면 된다.

- 이동 시키고 난 후 미친 아두이노와 만났는지만 확인해 주어 만났다면 게임을 끝내주면 된다.

 

🔹 미친 아두이노를 이동시킨다

- 미친 아두이노 리스트에서 하나씩 꺼내며 확인해 준다.

- 미친 아두이노는 이동하지 않는 경우가 없다는 부분의 예외처리를 조심하자.

- 미친 아두이노가 이동 후에 한 공간에 2개 이상의 미친 아두이노가 모였는지 확인해 주는 과정이 필요하므로 이동 후 미친 아두이노의 개수를 세 주는 배열을 만들어 주었다.

- 현재 미친 아두이노는 이동 할 예정이므로 '.'으로 변경해 준다.

- 이동 중에 종수의 아두이노를 만나면 게임을 끝내주면 된다.

 

🔹 한 공간에 2개 이상의 미친 아두이노가 있다면 폭발하여 사라진다.

- 개수를 미리 저장해 주었으므로 탐색하며 미친 아두이노가 1개만 있는 위치를 찾아준다.

- 해당 위치에 대한 노드 정보만 다시 미친 아두이노 리스트에 담아준다.

 

 

코드

//8972: 미친 아두이노
import java.io.*;
import java.util.*;
 
public class Main {
 
    static int r, c;
    static char[][] board;
    static int[] dx = {0, 1, 1, 1, 0, 0, 0, -1, -1, -1};
    static int[] dy = {0, -1, 0, 1, -1, 0, 1, -1, 0, 1};
    static LinkedList<Node> craze_arduino;
    static Node arduino;
 
    public static void main(String[] args) throws IOException {
 
        //입력
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        String str = bf.readLine();
        StringTokenizer st = new StringTokenizer(str);
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
 
        board = new char[r][c];
        craze_arduino = new LinkedList<>(); //미친 아두이노의 위치 저장
        for(int i = 0; i < r; i++) {
            str = bf.readLine();
            for(int j = 0; j < c; j++) {
                board[i][j] = str.charAt(j);
 
                if(board[i][j] == 'R') craze_arduino.add(new Node(i, j));
                else if(board[i][j] == 'I') arduino = new Node(i, j);
            }
        }
        String direction = bf.readLine();
        //입력 끝
 
        int count = 1; //움직인 횟수
        boolean is_lose = false;
        for(int k = 0; k < direction.length(); k++){
            //종수 아두이노 이동
            board[arduino.x][arduino.y] = '.';
            arduino.x = arduino.x + dx[direction.charAt(count - 1) - '0'];
            arduino.y = arduino.y + dy[direction.charAt(count - 1) - '0'];
 
            if(board[arduino.x][arduino.y] == 'R') {
                is_lose = true;
                break;
            }
            board[arduino.x][arduino.y] = 'I';
 
            //미친 아두이노 이동
            if(!move_craze_arduino()) {
                is_lose = true;
                break;
            }
            count++;
        }
 
        if(is_lose) System.out.println("kraj " + count);
        else print_board();
    }    
 
    public static boolean move_craze_arduino() {
        int[][] arduino_count = new int[r][c];
 
        int craze_arduino_size = craze_arduino.size();
        for(int i = 0; i < craze_arduino_size; i++) {
            Node current = craze_arduino.poll();
            board[current.x][current.y] = '.'; 
            
            int dir = find_close_dir(current);
            int nx = current.x + dx[dir];
            int ny = current.y + dy[dir];
            
            if(board[nx][ny] == 'I') return false;
            arduino_count[nx][ny]++;
        }
 
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                if(arduino_count[i][j] == 1) {
                    board[i][j] = 'R';
                    craze_arduino.add(new Node(i, j));
                }
            }
        }
        return true;
    }
 
    public static int find_close_dir(Node current) {
        int min = Integer.MAX_VALUE;
        int min_dir = -1;
        for(int i = 1; i <= 9; i++) {
            if(i == 5) continue; //미친 아두이노는 가만히 있는 경우가 없다.
            int nx = current.x + dx[i];
            int ny = current.y + dy[i];
            if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            
            int distance = Math.abs(nx - arduino.x) + Math.abs(ny - arduino.y);
            if(min > distance) {
                min = distance;
                min_dir = i;
            }
        }
        return min_dir;
    }
    
    public static void print_board() {
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                System.out.print(board[i][j]);
            }
            System.out.println();
        }
    }
 
    public static class Node {
        int x, y;
 
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}