[JAVA] 백준 - 탈출 (3055) - (BFS)

www.acmicpc.net/problem/3055

3055번: 탈출

 

"움직이는 미로 탈출" 과 똑같은 문제다.

 

onejunu.tistory.com/98

[JAVA] 백준 - 움직이는 미로 탈출 - 16954 ( BFS)

 

2차원 char 배열을 큐에 넣으면서 BFS 로직을 하면 되는 문제

 

주의할 점이 있는데 고슴도치가 움직이기전에 배열판을 먼저 움직여 줘야한다는 것이다.

 

그리고 다음 배열판을 기준으로 고슴도치가 이동할 수 있는지 없는지 체크해야한다.

 

 

 

 

# 자바코드

 

import java.util.LinkedList;
import java.util.*;

class Main{
    static int n,m;
    static int[][] dist;
    static int[] end = new int[2];
    static int[] start = new int[2];

    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        dist = new int[n][m];
        for(int i=0;i<n;i++) Arrays.fill(dist[i],-1);

        char[][] firstMap = new char[n][m];

        for(int i=0;i<n;i++){
            char[] temp = sc.next().toCharArray();
            for(int j=0;j<m;j++){
                firstMap[i][j] = temp[j];
                if(temp[j] == 'S'){
                    start[0] = i;
                    start[1]=  j;
                }
                if(temp[j] == 'D'){
                    end[0] = i;
                    end[1] = j;
                }
            }
        }


        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(start[0],start[1],firstMap));
        dist[start[0]][start[1]] = 0;

        while(!q.isEmpty()){
            Pair p = q.poll();

            char[][] nextMap = p.nextMap();

            for(int i=0;i<4;i++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                if(nx <0 || nx>=n || ny<0 || ny>=m ) continue;

                if(dist[nx][ny]==-1 && (nextMap[nx][ny]=='.' || nextMap[nx][ny]=='D')){
                    dist[nx][ny] = dist[p.x][p.y] + 1;
                    q.add(new Pair(nx,ny,nextMap));
                }
            }
        }

        System.out.println(dist[end[0]][end[1]]==-1?"KAKTUS":dist[end[0]][end[1]]);


    }

    static class Pair{
        int x,y;
        char[][] myMap;

        public Pair(int x,int y,char[][] map){
            this.x = x;
            this.y = y;
            myMap = new char[n][m];
            for(int i=0;i<n;i++){
                if (m >= 0) System.arraycopy(map[i], 0, myMap[i], 0, m);
            }
        }

        public char[][] nextMap(){
            char[][] nextMap = new char[n][m];
            for(int i=0;i<n;i++){
                if (m >= 0) System.arraycopy(myMap[i], 0, nextMap[i], 0, m);
            }

            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(myMap[i][j]=='*'){

                        for(int k=0;k<4;k++){
                            int nx = i + dx[k];
                            int ny = j + dy[k];

                            if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
                            if(myMap[nx][ny]=='.'){
                                nextMap[nx][ny] = '*';
                            }
                        }

                    }
                }
            }
            return nextMap;

        }

        public void printMap(){
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    System.out.print(myMap[i][j]);
                }
                System.out.println();
            }
            System.out.println();
        }
    }

}