[Gold III] 벽 타기 - 23563

문제 링크

성능 요약

메모리: 33392 KB, 시간: 628 ms

분류

0-1 너비 우선 탐색, 데이크스트라, 그래프 이론, 최단 경로

제출 일자

2024년 12월 18일 16:11:27

문제 설명

루시우는 높이가 $H$이고 너비가 $W$인 맵의 시작점에서 끝점까지 이동하려고 한다.

• 맵은 $H$개의 행과 $W$개의 열로 이루어진 격자판 모양이다. 각 칸은 벽 또는 빈칸이다.
• 루시우는 상, 하, 좌, 우 방향 인접한 칸으로 한 칸씩 이동할 수 있다. 벽으로는 이동할 수 없다.
• 루시우가 한 칸을 이동하는 데에는 1초가 걸린다.
• 하지만 루시우가 벽을 타고 이동하면 순식간에 (0초의 시간에) 상, 하, 좌, 우 방향 인접한 칸으로 이동할 수 있다.
• 어떤 빈칸의 상하좌우 중 하나가 벽이면 이 칸은 벽에 인접한 칸이라고 한다.
• 벽에 인접한 칸에서 벽에 인접한 칸으로 이동하면 벽을 타고 이동한다고 말한다.
  루시우가 맵의 시작점에서 끝점까지 이동하는 데 걸리는 최소 시간을 구하여라.

입력

첫째 줄에는 $H$와 $W$가 공백을 사이에 두고 주어진다. 맵은 $H$개의 행과 $W$개의 열로 이루어진 격자판 모양이다.

둘째 줄부터, $H$개의 줄에 걸쳐서 맵의 모습을 나타내는 $W$개의 문자가 주어진다.

• #는 벽을 뜻한다.
• .는 빈칸을 뜻한다.
• S는 맵의 시작점을 뜻한다. 시작점은 빈칸이다.
• E는 맵의 끝점을 뜻한다. 끝점은 빈칸이다.

출력

루시우가 맵의 시작점에서 끝점까지 이동하는 데 걸리는 최소 시간을 출력하라.

문제 풀이

union find와 bfs를 사용했다.

코드

Java 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int[] dr = {0, -1, 0, 1};
    static int[] dc = {-1, 0, 1, 0};
    static int H, W, visited[][], start[], end[];
    static int[] p;
    static char board[][];

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

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_23563_벽타기/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        board = new char[H][W];
        visited = new int[H][W];
        p = new int[H * W];

        for (int i = 0; i < H; i++) {
            String str = br.readLine();
            for (int j = 0; j < W; j++) {
                board[i][j] = str.charAt(j);
                visited[i][j] = Integer.MAX_VALUE;
                p[i * W + j] = i * W + j;
                if (board[i][j] == 'S') {
                    start = new int[]{i, j};
                    visited[i][j] = 0;
                }
                if (board[i][j] == 'E') {
                    end = new int[]{i, j};
                }
            }
        }

        for (int i = 1; i < H - 1; i++) {
            for (int j = 1; j < W - 1; j++) {
                if (board[i][j] != '#' && isNextToWall(i, j)) {
                    for (int k = 0; k < 4; k++) {
                        int nr = i + dr[k];
                        int nc = j + dc[k];
                        if (nr >= 1 && nr < H - 1 && nc >= 1 && nc < W - 1 && board[nr][nc] != '#' && isNextToWall(nr, nc)) {
                            union(i * W + j, nr * W + nc);
                        }
                    }
                }
            }
        }

        bfs(start);
        System.out.println(visited[end[0]][end[1]]);

        bw.flush();
        bw.close();
        br.close();
    }

    private boolean isNextToWall(int i, int j) {
        for (int k = 0; k < 4; k++) {
            int nr = i + dr[k];
            int nc = j + dc[k];
            if (nr >= 0 && nr < H && nc >= 0 && nc < W && board[nr][nc] == '#') return true;
        }
        return false;
    }

    private void union(int x, int y) {
        p[find(y)] = find(x);
    }

    private int find(int x) {
        if (p[x] != x) return p[x] = find(p[x]);
        return x;
    }

    private void bfs(int[] start) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        pq.offer(new int[]{start[0], start[1], 0});
        visited[start[0]][start[1]] = 0;

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int currTime = curr[2];

            if (currTime > visited[curr[0]][curr[1]]) continue;

            for (int k = 0; k < 4; k++) {
                int nr = curr[0] + dr[k];
                int nc = curr[1] + dc[k];

                if (nr <= 0 || nr >= H - 1 || nc <= 0 || nc >= W - 1 || board[nr][nc] == '#') continue;

                int time = currTime + 1;

                if (isNextToWall(curr[0], curr[1]) && isNextToWall(nr, nc) && find(curr[0] * W + curr[1]) == find(nr * W + nc)) {
                    time = currTime;
                }

                if (visited[nr][nc] > time) {
                    visited[nr][nc] = time;
                    pq.offer(new int[]{nr, nc, time});
                }
            }
        }
    }
}

---

C++ 코드