[Softeer] Lv3. GINI야 도와줘 (Java)

1. 문제

• 문제 링크 : Lv3. GINI야 도와줘
• 주제 : BFS

---

2. 풀이 과정 및 정리

예전에 비슷한 문제를 풀었던 기억이 나서 또 비슷하게 풀었다.

(문제 풀이 기록 - 3055번 탈출) https://soo-note.tistory.com/52

[TIL] Algorithm - 다익스트라 + 그래프 문제 풀이(BFS)

저번에는 파이썬으로 풀었는데 이번에 자바로 풀어보았다.

이번에도 핵심은 비오는 시간을 구하고 이에 따른 이동방법을 찾아 보는 방식으로 구했다.

즉, 2번의 BFS를 사용하여 문제를 해결했다.

 

저번에 기록했듯이 다음에는 한번의 BFS로 푸는 것을 도전해보아야겠다.

---

3. 코드

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

public class Main {

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

    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int r, c;
    static char[][] map;
    static int[][] rain_time;

    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());

        map = new char[r][c];
        rain_time = new int[r][c];
        
        Node start = new Node(0, 0);
        Node end = new Node(0, 0);
        ArrayList<Node> rain_first = new ArrayList<>();
        for(int i = 0; i < r; i++) {
            String s = br.readLine();
            for(int j = 0; j < c; j++) {
                map[i][j] = s.charAt(j);
                switch(map[i][j]) {
                    case 'W' :
                        start.x = i;
                        start.y = j;
                        map[i][j] = '.';
                        break;
                    case 'H' :
                        end.x = i;
                        end.y = j;
                        break;
                    case '*' :
                        rain_first.add(new Node(i, j));
                        break;
                }
            }
        }

        rain(rain_first);
        move(start, end);
    }

    // 각 위치에서 소나기가 내리기 시작하는 시간 구하기
    public static void rain(ArrayList<Node> rain_first) {
        Queue<Node> queue = new LinkedList<>();
        for(Node n : rain_first) {
            rain_time[n.x][n.y] = 1;
            queue.add(n);
        }

        while(!queue.isEmpty()) {
            Node current = queue.poll();
            for(int i = 0; i < 4; i++) {
                int nx = current.x + dir[i][0];
                int ny = current.y + dir[i][1];

                if(nx < 0 || nx >= r || ny < 0 || ny >= c) {
                    continue;
                }

                if(rain_time[nx][ny] == 0 && map[nx][ny] == '.') {
                    rain_time[nx][ny] = rain_time[current.x][current.y] + 1;
                    queue.add(new Node(nx, ny));
                }
            }
        }
    }

    // 비를 피해 차로 이동하는 시간 구하기
    public static void move(Node start, Node end) {
        int[][] count = new int[r][c];
        Queue<Node> queue = new LinkedList<>();

        count[start.x][start.y] = 1;
        queue.add(start);

        while(!queue.isEmpty()) {
            Node current = queue.poll();
            
            for(int i = 0; i < 4; i++) {
                int nx = current.x + dir[i][0];
                int ny = current.y + dir[i][1];

                if(nx < 0 || nx >= r || ny < 0 || ny >= c) {
                    continue;
                }

                if(count[nx][ny] > 0 || map[nx][ny] == 'X' || map[nx][ny] == '*') {
                    continue;
                }

                if(count[current.x][current.y] + 1 < rain_time[nx][ny] || rain_time[nx][ny] == 0) {
                    count[nx][ny] = count[current.x][current.y] + 1;
                    queue.add(new Node(nx, ny));
                }
            }
        }
        
        if(count[end.x][end.y] == 0) {
            System.out.println("FAIL");
        }
        else {
            System.out.println(count[end.x][end.y]-1);
        }
    }
}