[JAVA] 백준 q3055 - 탈출

3055번: 탈출

---

> 의식의 흐름

10일 전에 풀었던 문제를 복습할겸 풀었는데 계속 메모리 초과가 나서 멘탈이 탈탈,,,

wDeque에 Location을 추가하는 부분에서 두더지굴만 아니면 될거라는 생각에

if (map[nx][ny] != 'D') {
    visited[nx][ny] = true;
    map[nx][ny] = '*'; // 물로 변경시켜주기
    wDeque.add(new Location(nx, ny));
}

라고 작성했고 무한루프에 빠져서 메모리 초과가 나온 것 같다.
=> 아예 비어있는 곳만 다음 차례에 가도록 if(map[nx][ny] == '*')로 조건문을 수정하니 바로 통과

 

> 풀이

1. map을 채워주면서 'S'일 때, '*'일 때 각각의 위치를 sDeque과 wDeque에 담아준다.

• sDeque = 고슴도치 위치 담는 deque;
• wDeque = 물 위치 담는 deque;
• 위치는 Location 클래스 사용해서 나타낸다.
  • Location은 x(행 번호), y(열 번호)를 갖는 클래스

2. bfs 활용

    ** 이때, 물이 찰 예정인 곳은 고슴도치가 가지 못하므로 물을 먼저 4방향으로 퍼뜨리고 고슴도치를 이동시킨다. **

    1) time을 한 번 증가시키고 그 시간에 담겨있는 wDeque 내의 Location과 sDeque 내의 Location에 대해서만 이동을 수행해야한다.

    2) 다음으로 이동할 곳이 비어있는 곳('.')인 경우, 물('*')로 변경시켜주고 wDeque에 다음에 이동할 Location을 삽입한다.

    3) 물 이동이 모두 끝나면 고슴도치를 이동시킨다.
         다음으로 이동할 곳이 비어있는 곳('.')이고 방문한 적 없는 경우, sDeque에 다음에 이동할 Loacation을 삽입한다.

    4) sDeque이 비거나 비버 굴('D')에 도착할 때까지 1)~3) 과정을 반복한다.

3. bfs가 끝났을 때의 time 값에 따라 답을 출력한다.
    만약 time == -1인 경우, 비버 굴에 도착하지 못했으므로 "KAKTUS" 출력

    그 외의 경우, 비버 굴에 도착했으므로 time 값 출력

 

> 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static int R,C; // 행, 열
    public static char[][] map;
    public static boolean[][] visited;
    public static int[] dx = {1,-1,0,0};
    public static int[] dy = {0,0,1,-1};
    public static int time = 0;

    public static Deque<Location> sDeque = new ArrayDeque<>(); // 고슴도치 위치
    public static Deque<Location> wDeque = new ArrayDeque<>(); // 물 위치

    public static class Location{
        int x;
        int y;

        public Location(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        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];
        for(int i=0;i<R;i++){
            String input = br.readLine();
            for(int j=0;j<C;j++){
                char inputChar = input.charAt(j);
                map[i][j] = inputChar;
                if(inputChar=='S'){
                    visited[i][j] = true;
                    sDeque.add(new Location(i,j));
                }
                else if(inputChar=='*'){
                    wDeque.add(new Location(i,j));
                }
            }
        }

        bfs();
        if(time == -1)
            bw.write("KAKTUS");
        else
            bw.write(Integer.toString(time));

        bw.flush();

        br.close();
        bw.close();

    }

    public static void bfs(){
        while(!sDeque.isEmpty()) {
            time++;
            // 물 4방향 퍼짐
            int wDequeSize= wDeque.size();
            for(int j=0;j<wDequeSize;j++){
                Location nowWater = wDeque.poll();

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

                    if (nx < 0 || ny < 0 || nx >= R || ny >= C)
                        continue;

                    if (map[nx][ny] == '.') { // 비어있는 곳인 경우
                        visited[nx][ny] = true;
                        map[nx][ny] = '*'; // 물로 변경시켜주기
                        wDeque.add(new Location(nx, ny));
                    }
                }
            }

            // 고슴도치 이동
            int sDequeSize = sDeque.size();
            for(int j=0;j<sDequeSize;j++){
                Location nowS = sDeque.poll();

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

                    if (nx < 0 || ny < 0 || nx >= R || ny >= C)
                        continue;

                    if (map[nx][ny] == 'D') {
                        return;
                    }

                    if (map[nx][ny] == '.' && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        sDeque.add(new Location(nx, ny));
                    }
                }
            }
        }

        time = -1;
    }
}