백준 8972 (미친 아두이노) - java

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

8972번: 미친 아두이노

유형 : BFS + 구현 문제이다.

다음 단계에 맞춰 구현을 해주면 된다.

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

1,2번 과정

• 아두이노는 총 9번 방향(그대로 있는거)으로 이동할 수 있기 때문에 방향 배열을 다음과 같이 설정한다. 0번 인덱스는 비워준다.

• 종수의 이동은 구현이 간단하다. 문제에서 각 회차에 따라 이동 방향을 알려주기 때문에 그 방향으로 이동하면 된다.
  • 위 과정에서 주의할 점은 이동했다면 이동하기 전 위치를 '.'로 설정해 비워주는 것이다.
  • 이동 하고 나서 그 위치가 'R'이라면 게임을 종료한다.

    static boolean moveJ(int dir)
    {
        int nx = sx + dx[dir];
        int ny = sy + dy[dir];

        if(board[nx][ny] == 'R')
            return false;

        board[sx][sy] = '.';
        board[nx][ny] = 'I';

        sx = nx;
        sy = ny;

        return true;
    }

3번 과정 (거리 계산)

    static int cal(int cx,int cy,int x,int y)
    {
        return Math.abs(cx - x) + Math.abs(cy - y);
    }

 

4,5번 과정

• 미친 아두이노와 종수 아두이노 사이의 거리 : cal() 메소드를 통해 구현
• int[][] count 배열을 통해 이동하고 나서 해당 좌표의 로봇의 개수를 세준다.
• 미리 미친 아두이노들을 Queue에 저장해놓는다. 모든 아두이노들을 이동시키고 나서 2개 이상 있는 좌표는 Queue에 추가하지 않는다.

    static boolean moveC(int x,int y)
    {
        int[][] count = new int[n+1][m+1];

        while(!crazy.isEmpty())
        {
            Point cur = crazy.poll();
            int dis = 100000;
            int idx = 1;

            for(int i=1;i<=9;i++)
            {
                int tx = cur.x + dx[i];
                int ty = cur.y + dy[i];

                if(tx <1 || tx > n || ty < 1 || ty > m)
                    continue;

                int td = cal(tx,ty,x,y);

                if(td < dis)
                {
                    dis = td; // 가장 가까운 거리 계산
                    idx = i; // 해당 방향 설정
                }
            }

            int nx = cur.x + dx[idx];
            int ny = cur.y + dy[idx]; // 이동

            if(board[nx][ny] == 'I')
                return false; // 종수를 잡았을 경우 게임 종료

            count[nx][ny] +=1; // count 증가
        }

        board = new char[n+1][m+1]; // 배열 다시 그리기

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                board[i][j] = '.';

                if(count[i][j] == 1) {
                    board[i][j] = 'R';
                    crazy.add(new Point(i, j));
                }
            }
        }

        board[sx][sy] = 'I';

        return true;
    }

전체 코드

import java.util.*;
import java.io.*;

public class Main {
    static int n = 0;
    static int m = 0;
    static int l = 0;
    static int k = 0;

    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 char[][] board;

    static int sx;
    static int sy;

    static Queue<Point> crazy = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new char[n+1][m+1];

        for(int i=1;i<=n;i++)
        {
            String line = br.readLine();

            for(int j=1;j<=m;j++) {
                board[i][j] = line.charAt(j - 1);

                if (board[i][j] == 'I')
                {
                    sx = i;
                    sy = j;
                }

                if(board[i][j] == 'R')
                    crazy.add(new Point(i,j));
            }
        }
        String cal = br.readLine();


        boolean over = false;
        for(int i=0;i<cal.length();i++)
        {
            int cd = Integer.parseInt(cal.charAt(i)+"");

            boolean f = moveJ(cd);

            if(!f) {
                System.out.println("kraj " + (i + 1));
                over = true;
                break;
            }

            boolean s = moveC(sx,sy);

            if(!s){
                System.out.println("kraj "+(i+1));
                over = true;
                break;
            }

        }

        if(!over)
        {
            print();
        }

        br.close();
    }

    static boolean moveJ(int dir)
    {
        int nx = sx + dx[dir];
        int ny = sy + dy[dir];

        if(board[nx][ny] == 'R')
            return false;

        board[sx][sy] = '.';
        board[nx][ny] = 'I';

        sx = nx;
        sy = ny;

        return true;
    }

    static int cal(int cx,int cy,int x,int y)
    {
        return Math.abs(cx - x) + Math.abs(cy - y);
    }

    static void print()
    {
        StringBuilder sb = new StringBuilder();

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                sb.append(board[i][j]);
            }sb.append("\n");
        }

        System.out.println(sb);
    }

    static boolean moveC(int x,int y)
    {
        int[][] count = new int[n+1][m+1];

        while(!crazy.isEmpty())
        {
            Point cur = crazy.poll();
            int dis = 100000;
            int idx = 1;

            for(int i=1;i<=9;i++)
            {
                int tx = cur.x + dx[i];
                int ty = cur.y + dy[i];

                if(tx <1 || tx > n || ty < 1 || ty > m)
                    continue;

                int td = cal(tx,ty,x,y);

                if(td < dis)
                {
                    dis = td;
                    idx = i;
                }
            }

            int nx = cur.x + dx[idx];
            int ny = cur.y + dy[idx];

            if(board[nx][ny] == 'I')
                return false;

            count[nx][ny] +=1;
        }

        board = new char[n+1][m+1];

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                board[i][j] = '.';

                if(count[i][j] == 1) {
                    board[i][j] = 'R';
                    crazy.add(new Point(i, j));
                }
            }
        }

        board[sx][sy] = 'I';

        return true;
    }

}
class Point
{
    int x;
    int y;

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