[백준] 3055번 - 탈출 (Java)

 

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

3055번: 탈출

 

<문제분석>
지도는 R행 C열로 이루어짐.
비어있는 곳 '.'
물이 차있는 곳 '*'
돌은 'X'
비버의 굴은 'D'
고슴도치의 위치는 'S'

고슴도치는 매분마다 인접한 상/하/좌/우의 칸 하나로 이동할 수 있다.
물도 매분마다 인접한 비어있는 칸으로 확장한다. (이것도 상/하/좌/우?)
물과 고슴도치는 돌을 통과할 수 없다.
고슴도치는 물로 차있는 지역으로 이동할 수 없다.
물도 비버의 굴로 이동할 수 없다.
고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다.

고슴도치가 안전하게 비버의 굴로 이동하기 위한 최소 시간을 구하라.
이동할 수 없다면 "KAKTUS"를 출력한다.

 

<풀이>
1. 고슴도치의 이동과 물이 차는 것이 동시에 일어나야 하기 때문에 하나의 BFS탐색 함수에 동시에 일어나야 한다.
그러기 위해선 class에 좌표 뿐만 아니라 종류까지 저장해야 한다.
class Point {
  int x, y;
  char type; // 'D' or '*'
}

2. 처음 for문을 돌려서 D와 *를 찾아서 종류와 위치를 큐에 넣는다.
3. 물은 확장하면 map[][]에 직접 *로 넣고, 고슴도치는 visited[][]로 방문처리를 하자.
4. map은 char[][]로 사용하자.
5. 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 어떻게 구현할까?
  - 이동한 위치의 상/하/좌/우 인점에 물이 있으면 이동 못하도록 하자.
6. 고슴도치의 이동시간은 visited 배열을 int로 만들어서 갱신하자.

 

<주의점>
1. 처음 큐에 고슴도치보다 물의 위치가 먼저 들어가니 결과가 달라진다. 고슴도치를 먼저 큐에 넣어야 한다.

 

<코드>

import java.util.Scanner;
import java.io.IOException;
import java.util.Queue;
import java.util.LinkedList;

//[백준] 3055번 - 탈출 (Java)

public class Main {
    static int R, C;
    static char map[][];
    static int visited[][];

    class Point {
        int x;
        int y;
        char type;
        Point (int x, int y, char type) {
            this.x = x;
            this.y = y;
            this.type = type;
        }
    }
	public void InputData() throws IOException
	{
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();
        map = new char[R][C];
        for (int i=0; i<R; i++) {
            String s = sc.next();
            for (int j=0; j<C; j++) {
                map[i][j] = s.charAt(j);
            }
        }
	}

    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0, -1};
    // public void BFS(int x, int y) {
        
    //     Q.offer(new Point(x, y));
    //     visited[x][y] = true;
    //     while (!Q.isEmpty()) {
    //         Point now = Q.poll();
    //         for (int i=0; i<4; i++) {
    //             int nx = now.x + dx[i];
    //             int ny = now.y + dy[i];
    //             // 맵 범위를 벗어나면 무시
    //             if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue; 
    //             if (map[nx][ny] == 0) continue; // 방문한 곳이 바다면 무시
    //             if (visited[nx][ny]) continue; // 이미 방문한 곳이면 무시
    //             Q.offer(new Point(nx, ny)); // 큐에 삽입
    //             map[nx][ny] += group_num; // 맵에 그룹숫자 부여
    //             visited[nx][ny] = true; // 방문처리
    //         }
    //     }
    // }


	public void Solve() {
        Queue<Point> Q = new LinkedList<>();
        visited = new int [R][C];

        // 1. BFS 초기 설정 수행(고슴도치 삽입)
        for (int i=0; i<R; i++) {
            for (int j=0; j<C; j++) {
                if (map[i][j] == 'S') { // 고슴도치 지역을 먼저 큐에 삽입
                    Q.offer(new Point(i, j, map[i][j]));
                    visited[i][j] = 0;
                    break;
                }
            }
        }
        for (int i=0; i<R; i++) {
            for (int j=0; j<C; j++) {
                if (map[i][j] == '*') { // 물지역을 모두 큐에 삽입
                    Q.offer(new Point(i, j, map[i][j]));
                }
            }
        }
        // 2. BFS 탐색 실행
        while (!Q.isEmpty()) {
            Point now = Q.poll();
            //System.out.println("Q: x= "+now.x+", y= "+now.y+", type= "+now.type);
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue; // map 범위를 벗어나면 스킵
                if (map[nx][ny] == 'X') continue; // 방문지역이 돌이면 스킵
                if (map[nx][ny] == '*') continue; // 방문지역이 물이면 스킵
                // 2-1. 탐색주체가 고슴도치일 경우
                if (now.type == 'S') {
                    if (map[nx][ny] == 'D') { // 방문지역이 비버의 굴이면 탐색 종료
                        System.out.println(visited[now.x][now.y]+1);
                        return;
                    }
                    if (findNextWater(nx, ny)) continue; // 탐색지역 인근에 물이 있으면 스킵
                    Q.offer(new Point(nx, ny, now.type)); // 탐색지역이 유효하기에 큐에 삽입
                    visited[nx][ny] = visited[now.x][now.y]+1; // 방문거리 +1 증가
                    
                } else { // 2-2. 탐색주체가 물일 경우
                    if (map[nx][ny] == 'D') continue; // 방문지역이 비버의 굴이면 스킵
                    //System.out.println("  * nx= "+nx+", ny= "+ny);
                    Q.offer(new Point(nx, ny, now.type)); // 탐색지역이 유효하기에 큐에 삽입
                    map[nx][ny] = '*'; // 물 확산
                }
            }
        }
        System.out.println("KAKTUS"); // 경로를 못 찾으면 KAKTUS를 출력한다.
	}

    public boolean findNextWater(int x, int y) {
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue; // map 범위를 벗어나면 스킵
            if (map[nx][ny] == '*') return true;
        }
        return false;
    }
    
	public static void main(String[] args) throws IOException
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();
	}
}

 

<결과>

 

<수정점>

1. BFS의 메모리 초과 이슈는 큐에 너무 많은 add를 해서 발생한다. 적정 범위를 구하는 것이 중요하다.
  - 고슴도치 이동과 물 확산을 각각 별도의 큐를 생성해서 사용해야 한다. 
  - BFS탐색은 물 탐색은 현재의 물 큐사이즈(WQ.size())만큼만, 고슴도치 탐색은 현재의 고슴도치 큐 사이즈(Q.size())만큼만 돌려야 한다.

  - 평소처럼 while(!Q.isEmpty())를 사용하면 계속 추가되는 큐가 있기 때문에 범위가 초과되어 버리기 때문이다.
2. 큐에 넣는 작업을 InputData에서 바로 처리해서 이중 루프 돌리는 만큼의 시간복잡도를 세이브하자.
3. 물 이동 예측을 별도의 함수를 만들어서 체크 했는데 그럴 필요없이 물 이동을 먼저 하고 고슴도치를 이동시키면 된다.
  - 1 cycle : 1. 물 확산 -> 2. 고슴도치 이동, 이 사이클을 지키지 않고 큐에 있는 걸 연속으로 돌리면 결과가 이상하게 나온다.
4. 방문배열도 물과 고슴도치 둘다 따로 두자.
5. 이동거리를 방문배열 말고 클래스에서 관리하도록 하자.
class point {
    int x, y;
int move; // 이동거리
}

 

<수정 코드>

import java.util.Scanner;
import java.io.IOException;
import java.util.Queue;
import java.util.LinkedList;

//[백준] 3055번 - 탈출 (Java)

public class Main {
    static int R, C;
    static char map[][];
    static boolean visited[][];
    static Queue<Point> Q = new LinkedList<>();
    static Queue<Point> WQ = new LinkedList<>();
    
    class Point {
        int x;
        int y;
        int move;
        Point (int x, int y) {
            this.x = x;
            this.y = y;
        }
        Point (int x, int y, int move) {
            this.x = x;
            this.y = y;
            this.move = move;
        }
    }
	public void InputData() throws IOException
	{
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();
        map = new char[R][C];
        visited = new boolean[R][C];
        for (int i=0; i<R; i++) {
            String s = sc.next();
            for (int j=0; j<C; j++) {
                map[i][j] = s.charAt(j);
                if (map[i][j] == 'S') {
                    Q.offer(new Point(i, j, 0));
                    visited[i][j] = true;
                } else if (map[i][j] == '*') {
                    WQ.offer(new Point(i, j));
                }
            }
        }
	}

    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0, -1};
    static int ans = Integer.MAX_VALUE;
    public void BFS() {
        while (!Q.isEmpty()) {
            // 물 확산 BFS
            int wsize = WQ.size();
            //System.out.println("wsize= "+wsize);
            for (int t=0; t<wsize; t++) {
                Point now = WQ.poll();
                //System.out.println("*: x= "+now.x+", y= "+now.y);
                for (int i=0; i<4; i++) {
                    int nx = now.x + dx[i];
                    int ny = now.y + dy[i];
                    if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue; // map 범위를 벗어나면 스킵
                    if (map[nx][ny] == '.') { // 빈곳이면 물 확산
                        map[nx][ny] = '*'; // 물 확산
                        WQ.offer(new Point(nx, ny));
                        //System.out.println("  add *: nx= "+nx+", ny= "+ny);
                    }
                }
            }

            // 고슴도치 탐색 BFS
            int size = Q.size();
            //System.out.println("size= "+size);
            for (int t=0; t<size; t++) {
                Point now = Q.poll();
                //System.out.println("S: x= "+now.x+", y= "+now.y+", move= "+now.move);
                for (int i=0; i<4; i++) {
                    int nx = now.x + dx[i];
                    int ny = now.y + dy[i];
                    if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue; // map 범위를 벗어나면 스킵
                    if (visited[nx][ny]) continue; // 이미 방문했으면 스킵
                    if (map[nx][ny] == 'D') { // 방문지역이 비버의 굴이면 탐색 종료
                        //System.out.println("find D : "+ now.move+1);
                        ans = Math.min(ans, now.move+1);
                        return;
                    }
                    if (map[nx][ny] == '.') {
                        visited[nx][ny] = true;
                        Q.offer(new Point(nx, ny, now.move+1)); // 탐색지역이 유효하기에 큐에 삽입
                        int len = now.move+1;
                        //System.out.println("  add S: nx= "+nx+", ny= "+ny+", move= "+len);
                    }
                }
            }
            //System.out.println("----------------------------");
        }
    }
	public void Solve() {
        BFS();
        System.out.println(ans == Integer.MAX_VALUE?"KAKTUS":ans); // 경로를 못 찾으면 KAKTUS를 출력한다.
	}
    
	public static void main(String[] args) throws IOException
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();
	}
}

 

<결과>