[백준 Java] 3055 탈출

🔗 문제링크 🔗

3055번: 탈출

---

🌟 생각 흐름 - 개인적 풀이 방법 🌟

물이 이동하는 경로와, 고슴도치가 이동하는 경로를 생각한다.

한 턴을 기준으로 BFS를 이용하여 먼저 물을 이동시키고, 고슴도치가 이동하는 방식으로 알고리즘을 구현하였다.

 

쉽게 물을 이동시키기 위해 물의 좌표를 입력당시 큐에 넣어두고

고슴도치의 시작 위치 또한 큐에 넣어준다.

 

이후에 물을 이동시키면서 기존 BFS와 같이 큐에 추가하면서 이동시킨다. 

ㄴ 차이점은 visit배열을 따로 선언하는것이 아닌 map에서 물이 이동하는 경우는 그냥 '*'로 채워 물이 채워짐을 체크하면서 지나가면 된다.

 

고슴도치는 BFS와 동일하게 해결하면 된다. 

ㄴ visit배열에 이동했었던 고슴도치의 위치를 표기하고 이후에 같은 칸에 접근하지 못하도록 한다 ( 이것을 체크하지 않으면  힙 메모리 초과가 발생한다 ) 

---

🍳 코드 🍳

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static char[][] map;
    private static int row, col;
    private static Point start;
    private static final Queue<Point> waters = new LinkedList<>();
    private static final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());

        map = new char[row][col];
        for (int i = 0; i < row; i++) {
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < col; j++) {
                if (map[i][j] == 'S') start = new Point(i, j);
                else if (map[i][j] == '*') waters.add(new Point(i, j));
            }

        }
        int ans = bfs();
        System.out.println(ans == -1 ? "KAKTUS" : ans);
    }

    private static int bfs() {
        Queue<Point> q = new LinkedList<>();
        q.add(start);

        boolean[][] visited = new boolean[row][col];
        visited[start.x][start.y] = true;

        int depth = 0;
        while (!q.isEmpty()) {
            depth++;

            //물이 이동
            int size = waters.size();
            for (int i = 0; i < size; i++) {
                Point nowWater = waters.poll();

                for (int[] dir : dirs) {
                    int mvx = nowWater.x + dir[0];
                    int mvy = nowWater.y + dir[1];
                    if (mvx < 0 || mvy < 0 || row <= mvx || col <= mvy) continue;//범위를 벗어남
                    if (map[mvx][mvy] == '.') { //빈칸인 경우에만
                        waters.add(new Point(mvx, mvy));
                        map[mvx][mvy] = '*';
                    }
                }
            }


            size = q.size();
            //고슴도치 이동
            for (int i = 0; i < size; i++) {
                Point dochi = q.poll();

                for (int[] dir : dirs) {
                    int mvx = dochi.x + dir[0];
                    int mvy = dochi.y + dir[1];

                    if (mvx < 0 || mvy < 0 || row <= mvx || col <= mvy) continue;//범위를 벗어남
                    if (map[mvx][mvy] == 'D') return depth;
                    if (map[mvx][mvy] == '.' && !visited[mvx][mvy]) { //빈칸이고 방문되지 않은
                        q.add(new Point(mvx, mvy));
                        visited[mvx][mvy] = true;
                    }
                }
            }
        }
        return -1;

    }


    private static class Point {
        int x, y;

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