백준 3055 탈출 Java

구현, 시뮬레이션에 약한 것 같아서 그쪽 관련 문제만 풀어보다가

오랜만에 풀어본 BFS문제이다. 시뮬레이션 분류에서 발견했지만

BFS를 오랜만에 사용해서 실수를 좀 많이했던 문제이다.

 

돌은 X

물은 *

비버굴은 D

고슴도치는 S

 

물과 고슴도치는 상, 하, 좌, 우로 움직일 수 있고

물은 돌과 비버굴을 지날 수 없고

고슴도치는 물과 돌을 지날 수 없다.

 

1분에 한 칸씩 물과 고슴도치가 움직인다고할 때

고슴도치가 비버굴에 몸을 피하는 최소 시간을 출력하면 되는 문제이다.

 

문제 설명에서도 알 수 있듯이

물이 먼저 움직이고 고슴도치가 움직이는 로직으로 구현해주면

해결되는 문제이다.

상, 하, 좌, 우로 움직이고 최소시간을 구하는 것이기 때문에

당연하게 BFS를 사용해서 해결했다.

 

고슴도치의 위치를 담을 큐와

물의 위치를 담을 큐를 따로 만들었다.

 

오늘 실수했던 점은 BFS를 사용하면서

이미 방문했던 곳을 방문하지 않도록 하는 구현을

까먹었다는 점이다.. 

DFS나 BFS나 왔던 곳을 되돌아가면 메모리초과가 나는

당연한 사실을 까먹고 맞는데 왜 안되지...를 연발했던 자신을

반성하기 위해 글을 썼다.

급하게 작성하느라 지저분한 코드이므로 구현 방법만 보면 될 것 같다..

 

import java.util.*;
import java.io.*;
 
public class Q3055 {
    static Pos biber;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        char[][] map = new char[n][m];
        int[][] dist = new int[n][m];
        int[] tx = {1, -1, 0, 0};
        int[] ty = {0, 0, 1, -1};
        Queue<Pos> waterQ = new LinkedList<>();
        Queue<Pos> hedgehogQ = new LinkedList<>();
 
 
        for(int i=0; i<n; i++) {
            String input = br.readLine();
            for(int j=0; j<m; j++) {
                map[i][j] = input.charAt(j);
                if(map[i][j] == 'D') biber = new Pos(i, j);
                else if(map[i][j] == 'S') hedgehogQ.add(new Pos(i, j));
                else if(map[i][j] == '*') waterQ.add(new Pos(i, j));
            }
        }
 
        while(!hedgehogQ.isEmpty()) {
            int size = waterQ.size();
            while(size-- > 0) {
                Pos k = waterQ.poll();
                for(int i=0; i<4; i++) {
                    if(k.x+tx[i]>=0 && k.x+tx[i]<n && k.y+ty[i]>=0 && k.y+ty[i]<m) {
                        if(map[k.x+tx[i]][k.y+ty[i]] == '.' || map[k.x+tx[i]][k.y+ty[i]] == 'S') {
                            map[k.x+tx[i]][k.y+ty[i]] = '*';
                            waterQ.add(new Pos(k.x+tx[i], k.y+ty[i]));
                        }
                    }
                }
            }
            size = hedgehogQ.size();
            while(size-- > 0) {
                Pos k = hedgehogQ.poll();
                for(int i=0; i<4; i++) {
                    if(k.x+tx[i]>=0 && k.x+tx[i]<n && k.y+ty[i]>=0 && k.y+ty[i]<m) {
                        if(map[k.x+tx[i]][k.y+ty[i]] != 'X' && map[k.x+tx[i]][k.y+ty[i]] != '*') {
                            if(dist[k.x+tx[i]][k.y+ty[i]] == 0) {
                                dist[k.x+tx[i]][k.y+ty[i]] = dist[k.x][k.y]+1;
                                hedgehogQ.add(new Pos(k.x+tx[i], k.y+ty[i]));
                            }
                        }
                    }
                }
            }
        }
        String ans = (dist[biber.x][biber.y] == 0) ? "KAKTUS" : String.valueOf(dist[biber.x][biber.y]) ;
        System.out.println(ans);
    }
}
class Pos{
    int x;
    int y;
 
    public Pos(int x, int y) {
        this.x = x;
        this.y = y;
    }
}