3055 - 탈출 (Java)

 

---

 

문제

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

 

풀이

두 스텝으로 진행하면 된다.

 

1. 물을 먼저 퍼트린다.

 

2. 고슴도치가 이동할 수 있는 칸을 보고 이동처리를 한다.

 

※ 물 퍼트리기

 

우선 물 퍼트리는건, "*" 기준으로 상하좌우로 범위안에 들면서, 빈칸이어야 한다. (".")

이 경우에, 임시 배열을 만들어서 새롭게 퍼지는 칸을 체크하고,

마지막에 한번에 원본 배열에 물 값을 세팅해주면 된다.

 

※ 고슴도치 이동 처리

 

이거는 bfs 로 하면 되는데, 중요한게 있다.

한 단계마다 고슴도치가 이동 할 수 있는 걸 모두 체크해야하기에,

bfs 수행시 queue 에 들어가 있는, 같은 스텝의 데이터들을 모두 꺼내서 bfs 를 수행해야한다.

 

일반적으로는 bfs 는 queue에 있는값을 하나씩 꺼내면서 돌지만

이 상황은 한 스텝마다 물이 퍼지고, 그 스텝에 고슴도치가 어디를 갈 수 있는지 모두 확인해야하기 때문에

이전 스텝에 고슴도치가 갈 수 있었던 값들을 모두 queue에서 꺼내서, 다음에는 어디를 갈 수 있는지 확인해야 한다.

(여기서 말한 스텝은 걸린 시간을 의미함.)

 

Node currentNode = queue.removeFirst();
// 같은 시각대 애들을 모두 넣는다.
while(true){
    if(queue.isEmpty()) break;
    Node tempNode = queue.peekFirst();
    if(tempNode.t == currentNode.t){
        nodes.add(queue.removeFirst());
        continue;
    }
    break;
}

 

그 내용은 이 코드로 표현된다.

 

queue에서 값을 꺼낸다음에, 그 값과 같은 스텝 (시간) 을 가지는 값을 모두 꺼내서 한번에 bfs 를 수행해준다.

 

코드

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

public class Main {

    public static class Node {
        public int x;
        public int y;
        public int t;

        public Node(int x, int y, int t) {
            this.x = x;
            this.y = y;
            this.t = t;
        }
    }

    public static String[][] map;
    public static int[] dx = {0, 0, -1, 1};
    public static int[] dy = {1, -1, 0 ,0};
    public static Node startNode;
    public static Node endNode;
    public static int r;
    public static int c;

    public void solution() throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        map = new String[r][c];

        for(int i=0; i<r; i++){
            String[] temp = br.readLine().split("");
            for(int j=0; j<c; j++){
                map[i][j] = temp[j];
            }
        }


        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if(map[i][j].equals("S")) startNode = new Node(i, j, 0);
                if(map[i][j].equals("D")) endNode = new Node(i, j, 0);
            }
        }

        // 고슴도치가 bfs 를 수행한다.
        int result = process();
        if(result== -1){
            System.out.println("KAKTUS");
            return;
        }

        System.out.println(result);

    }


    public int process(){
        Deque<Node> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[r][c];
        queue.addLast(startNode);
        visited[startNode.x][startNode.y] = true;

        while (!queue.isEmpty()) {
            water(); // 물을 채운다.

            Node currentNode = queue.removeFirst();
            ArrayList<Node> nodes = new ArrayList<>();
            nodes.add(currentNode);

            // 같은 시각대 애들을 모두 넣는다.
            while(true){
                if(queue.isEmpty()) break;
                Node tempNode = queue.peekFirst();
                if(tempNode.t == currentNode.t){
                    nodes.add(queue.removeFirst());
                    continue;
                }
                break;
            }

            for (Node node : nodes) {
                int x = node.x;
                int y = node.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 && !visited[nx][ny] && (map[nx][ny].equals(".") || map[nx][ny].equals("D"))){
                        if(map[nx][ny].equals("D")) {
                            return node.t + 1;
                        }
                        queue.addLast(new Node(nx, ny, node.t + 1));
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        return -1;
    }

    public void water(){
        boolean[][] tempArray = new boolean[r][c];

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {

                // 물이 아니라면 넘어간다.
                if(!map[i][j].equals("*")) continue;

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

                    if(nx >= 0 && nx < r && ny >= 0 && ny < c && map[nx][ny].equals(".")){
                        tempArray[nx][ny] = true;
                    }
                }
            }
        }

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if(tempArray[i][j]){
                    map[i][j] = "*";
                }
            }
        }

    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

후기

 

단순한데 은근 단순하지 않다