[Algo] 백준 29703 펭귄의 하루 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/29703

메모리 : 144896KB

시간 : 816ms

언어 : Java 11

---

코드

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

public class Main {
    static class Node {
        int r, c;
        int cnt;

        Node(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
    }

    static int[][] vector = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
    static int N, M;
    static char[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new char[N][M];
        int[][][] dp = new int[N][M][2];
        Queue<Node> getFish = new LinkedList<>();
        Queue<Node> goHome = new LinkedList<>();
        boolean[][] fishCheck = new boolean[N][M];
        boolean[][] homeCheck = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j);
                if (map[i][j] == 'S') {
                    getFish.add(new Node(i, j, 1));
                    fishCheck[i][j] = true;
                } else if (map[i][j] == 'H') {
                    goHome.add(new Node(i, j, 1));
                    homeCheck[i][j] = true;
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        while (!getFish.isEmpty()) {
            Node n = getFish.poll();
            for (int k = 0; k < 4; k++) {
                int x = n.r + vector[k][0];
                int y = n.c + vector[k][1];
                if (x >= 0 && y >= 0 && x < N && y < M && !fishCheck[x][y] && map[x][y] != 'D') {
                    if (map[x][y] == 'F') {
                        dp[x][y][0] = n.cnt;
                    }
                    getFish.add(new Node(x, y, n.cnt + 1));
                    fishCheck[x][y] = true;
                }
            }
        }
        while (!goHome.isEmpty()) {
            Node n = goHome.poll();
            for (int k = 0; k < 4; k++) {
                int x = n.r + vector[k][0];
                int y = n.c + vector[k][1];
                if (x >= 0 && y >= 0 && x < N && y < M && !homeCheck[x][y] && map[x][y] != 'D') {
                    if (map[x][y] == 'F') {
                        dp[x][y][1] = n.cnt;
                    }
                    goHome.add(new Node(x, y, n.cnt + 1));
                    homeCheck[x][y] = true;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (dp[i][j][0] != 0 && dp[i][j][1] != 0) {
                    ans = Math.min(ans, dp[i][j][0] + dp[i][j][1]);
                }
            }
        }
        ans = (ans != Integer.MAX_VALUE) ? ans : -1;
        System.out.println(ans);
    }
}

 

풀이

시간초과로 한참 헤맸다🥴 물곡이를 찾을 때 마다 집에가는 bfs를 돌았더니 펭귄이 힘들었던게 틀림없다. 시작점에서 물곡이까지 가는 거리와 집에서 물곡이까지 가는 거리를 dp배열에 저장해 더한 최솟값을 찾았다. 집이나 시작점에서 물곡이까지 도달하지 못할 수 있기 때문에 dp를 3차원으로 정해 두 값이 모두 존재할때만, 즉 시작점-물곡이-집이 연결될때만 값을 구할 수 있도록 했다.