[JAVA]백준_8972_미친 아두이노

문제링크

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

8972번: 미친 아두이노

 

※주석은 출력 볼려고 넣어놓은 것이거나 간단한 설명 있는 부분이라서 지우고 보셔도 됩니다.

 

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

//먼저, 종수가 아두이노를 8가지 방향(수직,수평,대각선)으로 이동시키거나, 그 위치에 그대로 놔둔다.
//종수의 아두이노가 미친 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되며, 종수는 게임을 지게 된다.
//미친 아두이노는 8가지 방향 중에서 종수의 아두이노와 가장 가까워 지는 방향으로 한 칸 이동한다.
//즉, 종수의 위치를 (r1,s1), 미친 아두이노의 위치를 (r2, s2)라고 했을 때, |r1-r2| + |s1-s2|가 가장 작아지는 방향으로 이동한다.
//미친 아두이노가 종수의 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되고, 종수는 게임을 지게 된다.
//2개 또는 그 이상의 미친 아두이노가 같은 칸에 있는 경우에는 큰 폭발이 일어나고, 그 칸에 있는 아두이노는 모두 파괴된다.
public class Main_8972 {
    static int R, C;
    static int map[][];
    static ArrayList<Node> list;
    static Node node;
    static int dx[] = {1, 1, 1, 0, 0,0, -1, -1, -1};
    static int dy[] = {-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));
        String st[] = br.readLine().split(" ");

        R = Integer.parseInt(st[0]);
        C = Integer.parseInt(st[1]);
        map = new int[R][C];
        list = new ArrayList<>();

        for (int i = 0; i < R; i++) {
            String str = br.readLine();
            for (int j = 0; j < C; j++) {
                //map[i][j] = str.charAt(j);
                if (str.charAt(j) == '.') {
                    map[i][j] = 0;
                } else if (str.charAt(j) == 'I') {
                    map[i][j] = -1;
                    node = new Node(i, j);
                } else if (str.charAt(j) == 'R') {
                    map[i][j] = 1;
                    list.add(new Node(i, j));
                }
            }
        } //배열 입력

        String str = br.readLine();
//        dir = new int[str.length()];
//        for(int i=0,size=str.length();i<size;i++){
//            dir[i] = Integer.parseInt(String.valueOf(str.charAt(i)));
//        }//종수가 움직일 방향
        for (int d = 0, size = str.length(); d < size; d++) {
            int dir = str.charAt(d) - '0'; //현재 종수가 움직일 방향
//            System.out.println("======================================");
//            System.out.println(dir);

            //종수 움직이기
            // 종수의 아두이노가 미친 아두이노가 있는 칸으로 이동한 경우 게임 종료
            if (!moveJS(dir)) {
                System.out.println("kraj "+(d+1));
                return;
            }

            //미친 아두이노가 종수와 가장 가까워지는 방향으로 움직이기
            // 아두이노 움직일 시 다른 아두이노와 부딫히면 게임 종료
            if (!moveArduino()) {
                System.out.println("kraj "+(d+1));
                return;
            }

//            for (int i = 0; i < R; i++) {
//                System.out.println(Arrays.toString(map[i]));
//            }
        }

        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(map[i][j] == 0)
                    System.out.print(".");
                else if(map[i][j] == -1)
                    System.out.print("I");
                else System.out.print("R");
            }
            System.out.println();
        }
    }

    private static boolean moveArduino() {
        int size = list.size();
        for (int i = 0; i < size; i++) {
            int minLen = Integer.MAX_VALUE;
            int minDir = 0;
            int minRow=0,minCol=0;
            for (int d = 0; d < 9; d++) {
                //8방향 중 가장 거리가 작아지는 방향으로 이동
                int nx = list.get(i).x + dx[d];
                int ny = list.get(i).y + dy[d];

                if(nx<0 || ny<0 || nx>=R || ny>=C) continue;

                int len = Math.abs(node.x - nx) + Math.abs(node.y - ny);
                if (minLen > len) {
                    minDir = d;
                    minLen = len;
                    minRow = nx;
                    minCol = ny;
                }
            }
            map[list.get(i).x][list.get(i).y] = 0;
            list.get(i).x = minRow;
            list.get(i).y = minCol;
        }

        for (int i = 0; i < size; i++) {
            if (map[list.get(i).x][list.get(i).y] == -1) {
                return false;
            }
            map[list.get(i).x][list.get(i).y] += 1;
        }

        list.clear();
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(map[i][j] == 1){
                    list.add(new Node(i,j));
                }
                else if(map[i][j] >1){
                    map[i][j] = 0;
                }
            }
        }

        return true;
    }

    private static boolean moveJS(int dir) {
        int nx = node.x + dx[dir - 1];
        int ny = node.y + dy[dir - 1];

        if (map[nx][ny] > 0) { //종수가 움직였는데 미친 아두이노가 있는 칸으로 이동한 경우
            return false;
        } else {
            map[node.x][node.y] = 0;
            node.x = nx;
            node.y = ny; //종수 위치 업데이트
            map[node.x][node.y] = -1;
        }
        return true;
    }

    static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    } //좌표 저장할 노드
}

 

문제 시작하기 전에 R,C 선언 및

배열 저장할 map

ArrayList<Node>list 를 통해서 미친 아두이노를 리스트로 저장

Node node는 현재 종수의 아두이노 위치를 저장할 것이다.

dx,dy배열은 8방향을 저장해주었다.

8방향은 문제에 있는 1-8방향 순서대로 입력해주었다.

 

초반에는 배열 입력을 char로 받아서 해결해볼려고 하였으나

나중에 미친 아두이노 끼리 만났을 때 터뜨리는 것을 해결하기 위해 내가 임의로 숫자를 설정하여 int 배열로 받았다.

 

종수의 아두이노 I 부분은 -1로 셋팅해주었고

미친 아두이노 R은 1 나머지 빈 공간은 0으로 셋팅해주었다.

 

 

후에는 종수의 아두이노가 움직일 방향을 한개씩 받아주면서 움직였다.

 

1.종수가 움직이고 움직인 칸이 미친 아두이노가 있는 칸인지 검사

2. 미친 아두이노가 종수와 가장 가까워 지는 방향으로 움직이고

3. 미친 아두이노와 종수의 아두이노가  부딫힌 경우 게임 종료 || 미친 아두이노끼리 같은 장소 도달시 폭파 

 

위의 3가지 과정을 종수가 한칸 이동할 때마다 반복하여 주었다.

 

 

먼저 moveJS함수를 보겠다.

종수를 움직였을 경우를 check해주는 함수이다.

 

 

현재 입력받은 dir(움직일 방향)을 기준으로 움직여주었다.

종숙 움직였는데 미친 아두이노가 있는 칸으로 이동한 경우는 false를 return 아니면 true를 return 해주었다.

 

위에서 if(!moveJs(dir))를 통해 만났으면 중간에 종료되는 상황이므로 kraj를 출력해주고 아니면 다음 단계인 미친아두이노를 이동시켜준다.

 

 

이 함수에서 미친 아두이노의 이동이 이루어 진다.

일단 위에서 배열을 입력받을 때 미친 아두이노를 list에 저장해놓았으므로 list만큼 돌면서 확인해준다.

8방향을 탐색하면서 현재 위치에서 종수의 아두이노와 가장 가까워지는 방향을 구해준다.

 

이렇게 8방향을 다 돌고 나면 가장 작은 값이 구해진다.

중간중간 현재 minLen보다 len이 더 작은경우 minLen및 minDir(어느방향으로 가야 최소거리인지),minRow,minCol (최소좌표)를 업데이트 해준다.

 

8방향을 다 탐색한 후 현재 미친아두이노의 위치를 0 (빈 공간)으로 셋팅 해준 뒤 현재 미친 아두이노의 위치를 업데이트 해준다 (가야할 위치로)

 

 

그리고 모든 미친 아두이노의 움직일 dir를 다 구했으면

위의 for문을 돌리면서 움직일 곳으로 채워준다.

만약 종수의 아두이노를 만나면 return false를 해주었고

map[lsit.get(i).x][list.get(i).y] +=1를 해주어서 

나중에 map에서 1이상의 수가 있으면 미친 아두이노가 같은 칸에서 만났는 경우이므로 폭파를 시켜주었다.

 

그리고 현재 미친 아두이노가 저장되어있는 list를 비워준 뒤

배열을 처음부터 돌면서 == 1 이면 새로 갱신된 미친 아두이노를 다시 list에 담아두고

1 이상인 경우 미친 아두이노 여러개가 같은 칸에 존재하는 경우이므로 폭파를 시켜주기 위해 0으로 셋팅해주고 list에는 따로 추가하지 않는다.

 

 

이 과정을 통해 중간에 게임에서 진 경우에는 kraj를 출력하게 되고

움직일 방향을 모두 다 움직였으면 배열을 다시 출력해주면 된다.!!