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

문제링크

3055번: 탈출

 

 

접근한 방법

• 두 개의 노드 간의 거리를 구하는 문제이므로, bfs로 접근해보았다.

 

---

풀이방법

BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문에, 이 문제는 BFS를 이용했을 때 효과적이다.

 

물이 번지는 것도 고려해야하므로, 물의 시작지점부터 BFS를 수행한다.

물이 번지는 동작이 수행되었으면 그 이후로

시작지점(고슴도치가 있는 좌표)에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣는다.
특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 배열에 넣는다.

 

---

소스코드 작성 방법

• 맵의 크기(r, c)을 전역 필드로 선언한다.
• 맵의 정보(map), 방문 여부 및 거리(visited)도 전역 필드로 선언한다.
• 고슴도치의 처음 위치(sr, sc)와 탈출가능할 때 비버의 위치(dr, dc)를 전역 필드로 선언한다.
• 방향 배열 dx, dy로 상 좌 하 우 움직임을 저장한다.
• 탈출 성공 여부(isSuccess)를 전역 필드로 선언한다.
• 물의 위치를 담는 큐(waterQ)와 고슴도치의 위치(goQ)를 담는 큐를 전역 필드로 선언한다.
• 행과 열의 index를 저장할 수 있는 클래스를 선언한다.

 

• 주의사항 1 (입력받을 때)
• * 문자를 만날 때마다 불의 위치를 담는 큐에 좌표 객체를 넣어준다.
• S 문자를 만나면 고슴도치의 위치를 선언하였던 전역 필드에 넣어준다.
• D 문자를 만나면 비버의 위치를 선언하였던 전역 필드에 넣어준다.
• visited 배열을 -1로 초기화해준다.

 

• bfs 메소드를 선언하여 아래와 같이 처리해준다.
• 큐에 맨 처음 고슴도치 좌표의 객체를 넣어준다.
• 처음 칸도 지나는 것에 포함되므로 visited[sr][sc] = 0 로 처리해주어, 방문 처리 및 거리를 저장한다.
• while문으로 물의 위치를 담은 큐나 고슴도치의 위치를 담은 큐에 남아있는 게 없을 때까지 탐색을 수행한다.
• 물의 위치를 담은 큐와 고슴도치의 위치를 담은 큐를 나누어서 다음과 같이 수행한다.
• 나누어서 수행을 해야하므로, 물의 위치를 담은 큐의 크기만큼 물이 번지는 과정을 먼저 수행한다.
  • waterQ.poll()로 큐에서 현재 좌표 객체를 꺼낸다.
  • 반복문으로 현재 좌표에서 4방향으로 탐색을 수행한다.
  • 이 때, 다음으로 탐색할 좌표가 탐색할 맵의 크기를 벗어나거나 이미 물이 있거나(*) 돌이어서(X) 진행하지 못할 시 continue로 넘어간다.
  • 맵의 값이 '.'이고 아직 방문하지 않았다면(visited의 좌표가 -1이라면) 물이 지나간 자리를 물로 표시하고 물의 위치를 담은 큐에 다음 좌표의 객체를 넣어준다.
• 다음은 고슴도치의 위치를 담은 큐의 크기만큼 고슴도치가 빠져나갈 수 있는 과정을 탐색한다.
  • goQ.poll()로 큐에서 현재 좌표 객체를 꺼낸다.
  • 반복문으로 현재 좌표에서 4방향으로 탐색을 수행한다.
  • 이 때, 다음으로 탐색할 좌표가 탐색할 맵의 크기를 벗어나거나 이미 물이 있거나(*) 돌이어서(X) 진행하지 못할 시 continue로 넘어간다.
  • 다음으로 탐색할 좌표가 비버의 위치일 때 (D) isSuccess를 true로 처리하고
    그리고 visited[goNextR][goNextC]에 visited[goCur.r][goCur.c] + 1을 저장한다. (현재까지의 칸 수 + 1)
  • return으로 반복문을 빠져나온다.
  • 맵의 값이 '.'이고 아직 방문하지 않았다면(visited의 좌표가 -1이라면) visited[goNextR][goNextC]에 visited[goCur.r]][goCur.] + 1을 저장하여 거리의 정보를 넣어준다. (현재까지의 칸 수 + 1)
    큐에 다음 좌표의 객체를 넣어준다.

 

소스코드

package baekjoon.dfs_bfs;
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Q_3055_Escape_20210728 {
    public static int r,c;
    public static int sr, sc, dr, dc; // 고슴도치 위치와 비버의 위치
    public static char[][] map;
    public static int[][] visited;
    public static Queue<Pair> waterQ, goQ;
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};
    public static boolean isSuccess;

    public static void bfs(){
        goQ.add(new Pair(sr, sc));
        map[sr][sc] = '.';
        visited[sr][sc] = 0;

        while (!goQ.isEmpty() || !waterQ.isEmpty()) {

            int waterSize = waterQ.size();
            for (int water = 0; water < waterSize; water++) {
                Pair waterCur = waterQ.poll();

                for(int i=0 ; i<4 ; i++) {
                    int waterNextR = waterCur.r + dx[i];
                    int waterNextC = waterCur.c + dy[i];

                    if (waterNextR < 0 || waterNextR >= r || waterNextC < 0 || waterNextC >= c) continue;


                    if (map[waterNextR][waterNextC] == 'X' || map[waterNextR][waterNextC] == '*') continue;

                    if (map[waterNextR][waterNextC] == '.') {
                        map[waterNextR][waterNextC] = '*';
                        waterQ.add(new Pair(waterNextR, waterNextC));
                    }
                }
            }


            int goSize = goQ.size();
            for (int go = 0; go < goSize; go++) {
                Pair goCur = goQ.poll();

                for(int i=0 ; i<4 ; i++) {
                    int goNextR = goCur.r + dx[i];
                    int goNextC = goCur.c + dy[i];
                    if (goNextR < 0 || goNextR >= r || goNextC < 0 || goNextC >= c) continue;
                    if (map[goNextR][goNextC] == 'X' || map[goNextR][goNextC] == '*') continue;
                    if (map[goNextR][goNextC] == 'D') {
                        isSuccess = true;
                        visited[goNextR][goNextC] = visited[goCur.r][goCur.c] + 1;
                        return;
                    }
                    if (map[goNextR][goNextC] == '.' && visited[goNextR][goNextC] == -1) {
                        goQ.add(new Pair(goNextR, goNextC));
                        visited[goNextR][goNextC] = visited[goCur.r][goCur.c] + 1;
                    }
                }
            }
        }
    }

    public static void main (String[] args) throws IOException {
        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 int[r][c];
        waterQ = new LinkedList<>();
        goQ = new LinkedList<>();

        for (int i = 0; i < r; i++) {
            String temp = br.readLine();
            for (int j = 0; j < c; j++) {
                map[i][j] = temp.charAt(j);
                visited[i][j] = -1;
                if(map[i][j] == 'S'){
                    sr = i;
                    sc = j;
                }
                if(map[i][j] == 'D'){
                    dr = i;
                    dc = j;
                }
                if(map[i][j] == '*'){
                    waterQ.add(new Pair(i, j));
                }
            }
        }

        bfs();
        if(isSuccess){
            bw.write(visited[dr][dc]+"");
        } else{
            bw.write("KAKTUS");
        }

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

    static class Pair{
        int r;
        int c;

        public Pair(int r, int c){
            this.r = r;
            this.c = c;
        }
    }

    // debug
    public static void write(char[][] map) {
        for(int i=0 ; i<r ; i++) {
            for(int j=0 ; j<c ; j++) {
                System.out.print(map[i][j]+"");
            }
            System.out.println();
        }
        System.out.println();
    }
}