[백준][Java] 6129 - Obstacle Course

목차

 

문제 정보

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

6129번: Obstacle Course

난이도 : G4

유형 : 다익스트라, BFS

---

문제 풀이

우선순위 큐를 이용한 다익스트라 기법을 활용하여 풀었다. (0-1 BFS라고도 봐도 무방하다)

우선순위 큐에 들어 있는 데이터는 '회전 횟수'를 기준으로 하여 정렬된다.

 

기존 방향으로 진행하는 간선의 가중치는 '0',

90도로 회전하여 진행하는 간선은 가중치는 '1'로 가정한다.

---

코드

// author : DDing77

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {

    final int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int N;
    char[][] board;
    int[][] cntBoard;
    int startX;
    int startY;
    int endX;
    int endY;
    int res;

    private void execDijkstra() {
        PriorityQueue<Cow> pq = new PriorityQueue<>();
        cntBoard[startX][startY] = 0;

        for (int i = 0; i < dir.length; i++) {
            int nX = startX + dir[i][0];
            int nY = startY + dir[i][1];

            if (isRange(nX, nY)) {
                pq.add(new Cow(nX, nY, i, 0));
                cntBoard[nX][nY] = 0;
            }
        }

        while (!pq.isEmpty()) {
            Cow cur = pq.poll();

            if (board[cur.x][cur.y] == 'B') {
                continue;
            }

            for (int i = 0; i < dir.length; i++) {
                int nextDirection = (cur.directionIdx + i) % dir.length;
                int nX = cur.x + dir[nextDirection][0];
                int nY = cur.y + dir[nextDirection][1];

                if (isRange(nX, nY)) {
                    int nextChangeDirectionCount = cur.changeDirectionCount;
                    if (nextDirection != cur.directionIdx) {
                        nextChangeDirectionCount++;
                    }

                    if (cntBoard[nX][nY] >= nextChangeDirectionCount) {
                        pq.add(new Cow(nX, nY, nextDirection, nextChangeDirectionCount));
                        cntBoard[nX][nY] = nextChangeDirectionCount;
                    }
                }
            }
        }
    }

    private boolean isRange(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N && board[x][y] != 'x';
    }

    private void solution() {
        execDijkstra();
        System.out.println(cntBoard[endX][endY]);
    }

    private void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        board = new char[N][N];

        startX = -1;
        startY = -1;
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < N; j++) {
                board[i][j] = input.charAt(j);
                if (board[i][j] == 'A') {
                    startX = i;
                    startY = j;
                    continue;
                }
                if (board[i][j] == 'B') {
                    endX = i;
                    endY = j;
                }
            }
        }

        cntBoard = new int[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(cntBoard[i], Integer.MAX_VALUE);
        }

        res = 0;
    }

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

    static class Cow implements Comparable<Cow> {
        int x;
        int y;
        int directionIdx;
        int changeDirectionCount;

        public Cow(int x, int y, int directionIdx, int changeDirectionCount) {
            this.x = x;
            this.y = y;
            this.directionIdx = directionIdx;
            this.changeDirectionCount = changeDirectionCount;
        }

        @Override
        public int compareTo(Cow o) {
            return Integer.compare(this.changeDirectionCount, o.changeDirectionCount);
        }
    }
}