[백준 BOJ/Gold IV] 3055번 : 탈출

 

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

3055번: 탈출

 

 

1

처음 입력받을 때 물 위치, 고스도치 위치를 각각 큐에 담아준다

또한 굴의 위치를 알아두기 위해 굴의 행, 열을 a, b에 각각 저장해둔다

        for(int i = 0; i < R; i++) {
            String[] str2 = br.readLine().split("");
            for(int j = 0; j < C; j++) {
                map[i][j] = str2[j];
                if (map[i][j].equals("*")) water.addLast(new int[] {i, j});
                else if (map[i][j].equals("S")) position.addLast(new int[] {i, j});
                else if (map[i][j].equals("D")) {
                    a = i;
                    b = j;
                    // D의 위치 저장
                }
            }
        }

 

 

2

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 
즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다.

→ 먼저 물이 어떻게 찰 예정인지 확인한 후에 물이 차지 않을 칸으로 고슴도치가 이동할 수 있는 것이다

그래서 bfs의 while문을 돌때마다 매번 물이 어떻게 차게될지를 setWater를 통해 확인해서 지도를 변경해준다

 

static void setWater() {
        int size = water.size();

        for (int i = 0; i < size; i++) { // 들어온 순간 큐에 있는거만 확인
            int[] xy = water.pollFirst();
            int x = xy[0];
            int y = xy[1];

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

                if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
                    if (map[nx][ny].equals(".")) {
                        map[nx][ny] = "*";
                        water.addLast(new int[] {nx, ny});
                    }
                }
            }
        }
    }

- 큐는 이후에 계속 추가되기 때문에 setWater에 들어가는 순간 큐에 들어있던거만 검사할 수 있게 size를 확인해서 그만큼만 돌려준다

- 상하좌우 확인하여 비어있는 곳(.)을 모두 물로 바꾼다

 

 

3

static void bfs() {
        while (!position.isEmpty()) {

            setWater(); // 물 퍼진 후 지도 모습 확인

            int size = position.size();
            for (int i = 0; i < size; i++) { // 들어온 순간 큐에 있는거만 확인
                int[] xy = position.pollFirst();
                int x = xy[0];
                int y = xy[1];

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

                    if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
                        if (map[nx][ny].equals(".")) {
                            map[nx][ny] = "S";
                            time[nx][ny] = time[x][y] + 1;
                            position.addLast(new int[] {nx, ny});
                        } else if (map[nx][ny].equals("D")) {
                            time[nx][ny] = time[x][y] + 1;
                        }
                    }
                }

                if (time[a][b] != 0) { // D까지 도달했다면
                    return;
                }
            }
        }
    }

- time은 최소 시간을 담기 위해 만든 배열이다 map이 String 배열이라 숫자를 넣고 계산해주며 채워주기가 어려워서 따로 만들게 된 것이다.

- 고슴도치 위치에서 상하좌우를 확인해서 이동할 수 있는 구역이라면 고슴도치로 채워주고, 이때 이동하는 구역에 해당하는 위치와 같은 time 배열에는 이전 time값에 1씩 더해준다

이러면 굴에 도착하는 순간 가장 빠르게 도착하는 시간을 알수있다(time[a][b])

 

 

4

bfs();

        if (time[a][b] == 0) {
            System.out.println("KAKTUS");
        } else {
            System.out.println(time[a][b]);
        }

- bfs를 모두 돌고 온 후

만약 굴의 위치와 같은 위치의 time값이 0이라면 굴에 도착하지 못했다는거니까 "KAKTUS"를 출력하고, 그렇지않다면 time[a][b] 를 출력해주면 된다

 

 

 

⭐⭐

처음 제출했을 때는 "메모리 초과"가 나왔다

어떤걸 바꿀지 고민해보다가 바꾼게 이부분이다

 

setWater 

	if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
                    if (map[nx][ny].equals(".")) {
                        map[nx][ny] = "*";
                        water.addLast(new int[] {nx, ny});
                    }
                }

 

처음 제출때는 이랬다 ↓

	if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
                    if (!map[nx][ny].equals("X") && !map[nx][ny].equals("D")) { // 돌 or 굴 아니면 물 퍼질 수 있음
                        map[nx][ny] = "*";
                        water.addLast(new int[] {nx, ny});
                    }
                }

 

물은 돌로 막혀있는 부분이 아니거나 굴이 아니라면 퍼질 수 있어서 저렇게 조건을 넣었던거다

고슴도치는 한 곳을 선택해서 이동하긴하지만 일단 이동할 수 있는 곳은 모두 다 S로 표시해놓는데, 물이 S를 만났을 때는 고슴도치가 그 경로로 이동하지 않았다고 생각하고 물이 퍼져도 되는 구역으로 여겨도 되기 때문이다

(흠 글로는 내 생각을 설명못하겠다,,)

 

메모리 초과가 되고 생각해보니까 .이었다가 S 였다가 다시 물만나면 * 되고 이런게 불필요한 과정이라고 생각됐다 물도 .으로 비어있는 곳만 퍼지는걸 확인해도 충분할 거라는 생각이 들었고 이부분을 고쳐줬더니 메모리 초과가 해결되었다!!!

중복작업을 줄이고 넘겨도 되는 부분은 넘기는것이 메모리를 아끼는 비결(?

 

 

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int R;
    static int C;
    static String[][] map;
    static int[][] time;
    static Deque<int[]> water;
    static Deque<int[]> position;
    static int a;
    static int b;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str1 = br.readLine().split(" ");
        R = Integer.parseInt(str1[0]);
        C = Integer.parseInt(str1[1]);
        map = new String[R][C];
        time = new int[R][C];
        water = new ArrayDeque<>();
        position = new ArrayDeque<>();

        for(int i = 0; i < R; i++) {
            String[] str2 = br.readLine().split("");
            for(int j = 0; j < C; j++) {
                map[i][j] = str2[j];
                if (map[i][j].equals("*")) water.addLast(new int[] {i, j});
                else if (map[i][j].equals("S")) position.addLast(new int[] {i, j});
                else if (map[i][j].equals("D")) {
                    a = i;
                    b = j;
                    // D의 위치 저장
                }
            }
        }
        //System.out.println(Arrays.deepToString(map));

        bfs();

        if (time[a][b] == 0) {
            System.out.println("KAKTUS");
        } else {
            System.out.println(time[a][b]);
        }

    }


    static void bfs() {
        while (!position.isEmpty()) {

            setWater(); // 물 퍼진 후 지도 모습 확인

            int size = position.size();
            for (int i = 0; i < size; i++) { // 들어온 순간 큐에 있는거만 확인
                int[] xy = position.pollFirst();
                int x = xy[0];
                int y = xy[1];

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

                    if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
                        if (map[nx][ny].equals(".")) {
                            map[nx][ny] = "S";
                            time[nx][ny] = time[x][y] + 1;
                            position.addLast(new int[] {nx, ny});
                        } else if (map[nx][ny].equals("D")) {
                            time[nx][ny] = time[x][y] + 1;
                        }
                    }
                }

                if (time[a][b] != 0) { // D까지 도달했다면
                    return;
                }
            }
        }
    }

    static void setWater() {
        int size = water.size();

        for (int i = 0; i < size; i++) { // 들어온 순간 큐에 있는거만 확인
            int[] xy = water.pollFirst();
            int x = xy[0];
            int y = xy[1];

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

                if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
                    if (map[nx][ny].equals(".")) {
                        map[nx][ny] = "*";
                        water.addLast(new int[] {nx, ny});
                    }
                }
            }
        }
    }
}