[백준] | JAVA, 자바 | 3055번 - 탈출

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

---

문제 요약 :

1. 50보다 작거나 같은 자연수 R과 C가 주어진다.

2. R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

2-1. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

3. 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽)

4. 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해 있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다.

5. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

5-1. 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

6. 티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

---

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

public class Main {
    static class Coordinate {
        int x;
        int y;

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

    private static int R, C;
    private static char[][] map;
    private static Queue<Coordinate> waterQueue;
    private static Coordinate hedgehog;
    private static int[][] delta = {{-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 = new StringTokenizer(br.readLine());
        // 1. 50보다 작거나 같은 자연수 R과 C가 주어진다.
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];

        waterQueue = new ArrayDeque<>();

        // 2. R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.
        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                char c = line.charAt(j);
                if (c == '*') waterQueue.add(new Coordinate(i, j));
                if (c == 'S') {
                    hedgehog = new Coordinate(i, j);
                    c = '.';
                }
                map[i][j] = c;
            }
        }

        int cnt = move();

        // 6. 비버의 굴로 이동하기 위해 필요한 최소 시간 출력
        if (cnt == -1) {
            System.out.println("KAKTUS");
        } else {
            System.out.println(cnt);
        }

    }

    // 4. 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해 있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다.
    private static void expansionWater() {
        int size = waterQueue.size();
        Queue<Coordinate> nextQueue = new ArrayDeque<>();

        for (int i = 0; i < size; i++) {
            Coordinate temp = waterQueue.poll();

            for (int j = 0; j < 4; j++) {
                int nr = temp.x + delta[j][0];
                int nc = temp.y + delta[j][1];

                if (isRange(nr, nc) && map[nr][nc] == '.') {
                    map[nr][nc] = '*';
                    nextQueue.add(new Coordinate(nr, nc));
                }
            }
        }
        waterQueue.addAll(nextQueue);
    }

    // 3. 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽)
    private static int move() {
        Queue<Coordinate> moveList = new ArrayDeque<>();
        moveList.add(hedgehog);

        boolean[][] visited = new boolean[R][C];
        visited[hedgehog.x][hedgehog.y] = true;

        int cnt = 0;

        while (!moveList.isEmpty()) {

            int size = moveList.size();
            expansionWater();

            for (int i = 0; i < size; i++) {
                Coordinate temp = moveList.poll();

                if (map[temp.x][temp.y] == 'D') return cnt;

                for (int j = 0; j < 4; j++) {
                    int nr = temp.x + delta[j][0];
                    int nc = temp.y + delta[j][1];

                    if (!isRange(nr, nc) || visited[nr][nc]) continue;
                    // 5. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없다.
                    if (map[nr][nc] == 'X' || map[nr][nc] == '*') continue;
                    if (map[nr][nc] == 'D') return cnt + 1;

                    visited[nr][nc] = true;
                    moveList.add(new Coordinate(nr, nc));
                }
            }
            cnt++;
        }
        return -1;
    }

    private static boolean isRange(int nr, int nc) {
        return nr >= 0 && nr < R && nc >= 0 && nc < C;
    }
}

 

+ 추가 설명

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없기 때문에 코드에서는 물의 확산을 먼저 진행했음

---

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

public class Main {
    private static int R, C, MIN;
    private static char[][] map;
    private static int[][] delta = {{-1,0},{1,0},{0,-1},{0,1}}; // 상, 하, 좌, 우
    private static boolean[][] visited, waterVisited;
    static class Hedgehog{
        int x;
        int y;
        public Hedgehog(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    private static Hedgehog hedgehog;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        visited = new boolean[R][C];
        MIN = Integer.MAX_VALUE;

        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                char c = line.charAt(j);
                if (c == 'S') {
                    hedgehog = new Hedgehog(i, j);
                    c = '.';
                }
                map[i][j] = c;
            }
        }

        visited[hedgehog.x][hedgehog.y] = true;
        hedgehogMove(hedgehog.x, hedgehog.y, 0);

        if (MIN == Integer.MAX_VALUE) {
            System.out.println("KAKTUS");
        } else {
            System.out.println(MIN);
        }
    }

    private static void searchWater () {
        waterVisited = new boolean[R][C];
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == '*' && !waterVisited[i][j]) {
                    waterVisited[i][j] = true;
                    expansionWater(i,j);
                }
            }
        }
    }

    private static void expansionWater(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nr = x + delta[i][0];
            int nc = y + delta[i][1];

            if (isRange(nr, nc) && !waterVisited[nr][nc] && map[nr][nc] == '.') {
                waterVisited[nr][nc] = true;
                map[nr][nc] = '*';
            }
        }
    }
    private static void hedgehogMove(int x, int y, int cnt) {
        if (map[x][y] == 'X' || map[x][y] == '*') return;
        if (cnt > MIN) return;

        if (map[x][y] == 'D') {
            if (MIN > cnt) MIN = cnt;
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nr = x + delta[i][0];
            int nc = y + delta[i][1];

            if (isRange(nr, nc) && !visited[nr][nc]) {
                visited[nr][nc] = true;
                hedgehog.x = nr;
                hedgehog.y = nc;
                char[][] temp = new char[R][C];
                for (int n = 0; n < R; n++) {
                    for (int m = 0; m < C; m++) {
                        temp[n][m] = map[n][m];
                    }
                }
                searchWater();
                hedgehogMove(nr, nc, cnt + 1);
                visited[nr][nc] = false;
                hedgehog.x = x;
                hedgehog.y = y;
                for (int n = 0; n < R; n++) {
                    System.arraycopy(temp[n], 0, map[n], 0, C);
                }

            }
        }
    }

    private static boolean isRange(int nr, int nc) {
        return nr >= 0 && nr < R && nc >= 0 && nc < C;
    }

}

 

처음 풀었던 코드, BFS가 아니라 DFS방식으로 풀기도 했고 맵을 복사하는 과정에서 메모리를 많이 사용해 메모리 초과가 나왔었다.