[백준] 3055번 탈출 JAVA (자바) 풀이

문제 3055(BFS)

 

 :  티떱숲의 지도는 R행 C열로 이루어져 있다

    비어있는 곳은 .

    물이 차있는 지역은 *

    돌은 X

    비버의 굴은 D

    고슴도치의 위치 S

 

 :  매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동가능

    물도 매 분마다 인접한 비어있는 칸으로 확장

    물과 고슴도치는 돌을 통과할 수 없다

    고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다

 

 :  고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램

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

 

 

[입력]

 :  첫째 줄에 50보다 작거나 같은 자연수 R과 C

 :  다음 R개 줄에는 티떱숲의 지도 ('D'와 'S'는 하나)

  

 

 [출력]

 :  첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력
    (비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력)

 

 

 [문제접근]

 

 1. main메서드에서 미리 큐에 추가 VS 인자로 받아 bfs메서드에서 큐에 추가

• 본 게시글은 bfs메서드에서 큐에 추가한다
• 미리 큐에 추가하는 것과 차이점은 물의 위치다
  • bfs메서드에서 추가 = 물의 초기지점만 인자로 받아 bfs를 돌리며 물 위치를 파악
  • main메서드에서 추가 = 물의 모든 위치를 한 번에 큐로 추가해서 더욱 빠르다
• 미리 큐에 추가하는 것이 더 빠르지만 그럴 경우 bfs 메서드 내에서 물부터 먼저 처리를 하고 고슴도치 위치를 파악해야 해서 순서 챙기다 보니 오히려 더 복잡하다는 생각이 들었다 하지만 효율면에서는 미리 추가하는 것이 더 좋은 것 같다

 

2. 물 위치는 초기값 인자로 받을 때도 조건이 있다

• 리스트에 물의 모든 좌표를 추가하는 것이 아니라 하나의 좌표만 택해서 bfs를 돌리기 때문에 그냥 초기값만 택하기로 했다
  • if (WX == -1 && WY == -1) 이용
  • 객체를 -1로 초기화 한 것은 배열 인덱스가 0부터 시작하므로 겹치지 않기 위해 아예 음수로 지정했다
• 고슴도치는 무조건 하나는 있지만 물은 모두 없을 수도 있어서 bfs 인자로 받을 때 초기값인지 아닌지 조건을 걸었다
  • if (wx != -1 && wy != -1) 이용
  • 만약 초기값이라면 물이 아예 없다는 뜻

 

3. 위치 연산

• p[2]가 음수면 물인데 다음 위치가 . 일 경우 물 전염
• p[2]가 0 이상이면 고슴도치인데 다음 위치가 . 일 경우 고슴도치 이동
• 다음위치가 비어있다하더라도 그다음날 물이 차버린다면 이동할 수 없는데 그걸 구분해주는게 visit이다
  물이 이동하는건 현재 이동이 아니라 다음에 이동할 지점을 보는 것 
  이동이 가능하다면 해당 지점을 true 처리하므로 고슴도치는 아예 올 수 없다

 

 4. 종료조건

• 고슴도치 기준인 지 확인 (p[2]>=0)
• arr가 D인지 확인
• p[2]+1해서 출력하기

       

 5. 출력 배열 사용하지 말고 큐에다 넣어버리기

• 물은 시간을 계산하지 않기 때문에 p[2]에 -1로 지정
• 고슴도치는 시간을 계산해야하므로 p[2]에 0으로 지정해 차츰차츰 카운트한다
• 또한 p[2] 값을 통해 현재 물이 이동하고 있는지 고슴도치가 이동하고 있는지 구분한다

 

 

 [코드]

import java.io.*;
import java.util.*;

public class Main{
    static int dx[] = {0, 0, 1, -1};
    static int dy[] = {1, -1, 0, 0};
    static int R, C;
    static char arr[][];
    static boolean visit[][];

    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());
        arr = new char[R][C];
        visit = new boolean[R][C];

        int WX = -1, WY = -1, SX = -1, SY = -1; 

        for (int i = 0; i < R; i++) {
            arr[i] = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                if (arr[i][j] == '*') {
                    if (WX == -1 && WY == -1) {
                        WX = i;
                        WY = j;
                    }
                } else if (arr[i][j] == 'S') {
                    SX = i;
                    SY = j;
                }
            }
        }

        bfs(WX, WY, SX, SY);
    }
    
    static void bfs(int wx, int wy, int sx, int sy){
        Queue<int[]> q = new LinkedList<>();
        if (wx != -1 && wy != -1) { 
            q.add(new int[]{wx, wy, -1});
            visit[wx][wy] = true;
        }
           q.add(new int[]{sx, sy, 0});
            visit[sx][sy] = true;
        

        while(!q.isEmpty()){
            int[] p = q.poll();

            for(int i = 0; i < 4; i++){
                int nx = p[0] + dx[i];
                int ny = p[1] + dy[i];

                if (0 <= nx && nx < R && 0 <= ny && ny < C && !visit[nx][ny] && arr[nx][ny] != 'X') {
                    if (arr[nx][ny] == 'D' && p[2] >= 0) { 
                        System.out.println(p[2] + 1);
                        return;
                    }
                    
                    if (p[2] < 0 && arr[nx][ny] == '.') {  
                        arr[nx][ny] = '*';
                        visit[nx][ny] = true;
                        q.add(new int[]{nx, ny, -1});
                    } else if (p[2] >= 0 && arr[nx][ny] == '.') {  
                        arr[nx][ny] = 'S';
                        visit[nx][ny] = true;
                        q.add(new int[]{nx, ny, p[2] + 1});
                    }
                }
            }
        }
        System.out.println("KAKTUS"); 
    }
}

 

 [해설]
     

 :  static int dx[] = {0, 0, 1, -1};  상하좌우 이동 x좌표
    static int dy[] = {1, -1, 0, 0};  상하좌우 이동 y좌표
    static int R, C;  
    static char arr[][];
    static boolean visit[][];

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    R = Integer.parseInt(st.nextToken());  행
    C = Integer.parseInt(st.nextToken());  열
    arr = new char[R][C];  문자배열

    visit = new boolean[R][C];  방문기록

 :  int WX = -1, WY = -1, SX = -1, SY = -1;  물 좌표, 고슴도치 좌표 초기화

 :  for (int i = 0; i < R; i++) {
            arr[i] = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                if (arr[i][j] == '*') {  물 발견하면
                    if (WX == -1 && WY == -1) {  맨처음 위치만 저장
                        WX = i;
                        WY = j;
                    }
                } else if (arr[i][j] == 'S') {  고슴도치 위치저장
                    SX = i;
                    SY = j;
                }
            }
    }

 :  bfs(WX, WY, SX, SY);  bfs 실행

    
 :  static void bfs(int wx, int wy, int sx, int sy){
        Queue<int[]> q = new LinkedList<>();  큐선언
        if (wx != -1 && wy != -1) {  초기값이 들어오면 물이 아예 없는 것
            q.add(new int[]{wx, wy, -1});  초기값이 아닐 경우에만 큐에 추가
            visit[wx][wy] = true;  방문체크
        }
        q.add(new int[]{sx, sy, 0});  큐에 고슴도치 지점 추가 / 시간 count
        visit[sx][sy] = true;  방문체크
        

        while(!q.isEmpty()){
            int[] p = q.poll();  큐에서 뽑기

            for(int i = 0; i < 4; i++){  상하좌우 이동
                int nx = p[0] + dx[i];
                int ny = p[1] + dy[i];

                if (0 <= nx && nx < R && 0 <= ny && ny < C && !visit[nx][ny] && arr[nx][ny] != 'X') {
                    if (arr[nx][ny] == 'D' && p[2] >= 0) {  p[2]가 0이상이면 고슴도치 / 배열 D면 종료
                        System.out.println(p[2] + 1);  D 지점까지 가야하므로 +1해서 출력
                        return;
                    }
                    
                    if (p[2] < 0 && arr[nx][ny] == '.') {  물기준으로 볼 때 다음 위치가 빈 곳이면
                        arr[nx][ny] = '*';  물전염시키기
                        visit[nx][ny] = true;  방문체크
                        q.add(new int[]{nx, ny, -1});  큐에 추가 (-1 이라는건 물이란 뜻)
                    } 

                   

                    else if (p[2] >= 0 && arr[nx][ny] == '.') {  고슴도치 기준일 때 다음 위치 빈 곳이면
                        arr[nx][ny] = 'S';  고슴도치 다음위치로 이동
                        visit[nx][ny] = true;  방문체크
                        q.add(new int[]{nx, ny, p[2] + 1});  큐에 추가 (time+1 하기)
                    }
                }
            }
        }

        System.out.println("KAKTUS"); 탈출 불가면 출력

    }
  


 

 

이제 풀어보러 갈께요 :)

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

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