자바(백준) 3055 탈출

오답 노트 & 새로 알게 된 점

문제에서 "다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다"라는 말의 뜻을 잘 이해해야합니다.

 

이 말의 뜻은 물을 먼저 퍼지게 한 다음에 고슴도치를 움직이면 됩니다.

 

입력을 받을 때, 물이 나올 경우에 먼저 큐에 넣어줍니다.

그리고 나서 bfs를 시작할 때, 제일 마지막에 고슴도치의 위치를 넣어주었습니다.

 

bfs를 할 때는 물일 경우에는 문제 조건에 맞게 물을 퍼뜨리면 되고,

물이 아니면 고슴도치를 움직였습니다.

 

특히 물이 퍼질 때는 A 배열에 퍼지는 물의 위치를 기록해주었습니다.

 

코드

 

 

package bfs_dfs;

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

public class BOJ3055 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int row, col;
    static char A[][];
    static boolean visit[][];
    static Queue<Point> q = new ArrayDeque<>();
    static Point end, start;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, 1, -1};
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }

    static void pro() {
        bfs(start);
    }

    static void bfs(Point st) {
        q.offer(start);
        visit[st.x][st.y] = true;

        while (!q.isEmpty()) {
            Point p = q.poll();

            if(p.x == end.x && p.y == end.y){
                System.out.println(p.cnt);
                return;
            }

            if(A[p.x][p.y] == '*'){
                for (int i = 0; i < 4; i++) {
                    int X = p.x + dx[i];
                    int Y = p.y + dy[i];

                    if(!isRangeTrue(X,Y)) continue;
                    if(visit[X][Y]) continue;
                    if(A[X][Y] == 'D' || A[X][Y] == 'X') continue;

                    q.offer(new Point(X, Y, p.cnt));
                    visit[X][Y] = true;
                    A[X][Y] = '*';
                }
            }
            else{
                for (int i = 0; i < 4; i++) {
                    int X = p.x + dx[i];
                    int Y = p.y + dy[i];

                    if(!isRangeTrue(X,Y)) continue;
                    if(visit[X][Y]) continue;
                    if(A[X][Y] == '*' || A[X][Y] == 'X') continue;

                    q.offer(new Point(X, Y, p.cnt + 1));
                    visit[X][Y] = true;
                }
            }

        }
        System.out.println("KAKTUS");
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        row = atoi(st.nextToken());
        col = atoi(st.nextToken());

        A = new char[row][col];
        visit = new boolean[row][col];

        for (int i = 0; i < row; i++) {
            String s = br.readLine();
            for (int j = 0; j < col; j++) {
                A[i][j] = s.charAt(j);
                if(A[i][j] == '*') q.offer(new Point(i, j, 0));
                if(A[i][j] == 'D') end = new Point(i, j, 0);
                if(A[i][j] == 'S') start = new Point(i, j, 0);
            }
        }
    }

    static boolean isRangeTrue(int x, int y) {
        return x >= 0 && x < row && y >= 0 && y < col;
    }

    static class Point{
        int x, y, cnt;

        public Point(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}