[프로그래머스] 경주로 건설(java)

https://school.programmers.co.kr/learn/courses/30/lessons/67259

프로그래머스

bfs를 활용한 문제이다. 뿐만 아니라 각 거리의 최솟값도 알아야 하므로 dp의 개념도 필요하다.

 

핵심

일반 bfs와 다른 점은 이건 이전에 방향이 어디를 향하고 있는지가 중요하다. 직진을 하다가  좌회전이나 우회전을 할 경우 가중치가 달라지기 때문이다. 또한 기본적으로 방문한 곳은 다시 방문하지 않는 것이 일반적이지만, 더욱 작은 값으로 갈 수 있다면 그 값을 들고 다시 방문한다.

 

 

정답 코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    static int length;
    static boolean[][][] visited;
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};

    public int solution(int[][] board) {
        length = board.length;
        visited = new boolean[length][length][4];
        return bfs(board);
    }

    private int bfs(int[][] board) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(0, 0, -1, 0));
        int min = Integer.MAX_VALUE;

        while (!q.isEmpty()) {
            Node now = q.poll();

            if (now.y == length - 1 && now.x == length - 1) {
                min = Math.min(min, now.cost);
                continue;
            }

            for (int dir = 0; dir < 4; dir++) {
                int moveY = now.y + dy[dir];
                int moveX = now.x + dx[dir];

                if (validation(board, moveY, moveX)) {
                    continue;
                }

                int nextCost = now.cost;

                if (dir == now.dir || now.dir == -1) {
                    nextCost += 100;
                } else {
                    nextCost += 600;
                }

                if (!visited[moveY][moveX][dir] || board[moveY][moveX] >= nextCost) {
                    q.offer(new Node(moveY, moveX, dir, nextCost));
                    visited[moveY][moveX][dir] = true;
                    board[moveY][moveX] = nextCost;
                }
            }
        }
        return min;
    }

    private static boolean validation(int[][] board, int moveY, int moveX) {
        return moveY < 0 || moveY >= length || moveX < 0 || moveX >= length || board[moveY][moveX] == 1;
    }
}

class Node {
    int y;
    int x;
    int dir;
    int cost;

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

해설

우선 정사각형의 모양이고, 쉽게 그 길이를 사용하기 위해 length를 선언하였다.

중요한 점은 이전에 어디를 향하고 있었는지를 구분하기 위해 3차원 배열을 선언해 주었다.

이후 bfs를 시도한다. 첫 시작은 오른쪽과 아래로 향할 수 있는데 첫 번째 시작은 무조건 직진이기 때문에 dir에 -1을 넣어주었다.

이후 같은 방향이거나 처음 출발한(-1) 경우라면 100원이 더해진다. 아니라면 (같은 방향 -> 다른 방향) 이동 600원이 더해진다.

그리고 기본적으로 이미 방문한 곳은 방문을 하지 않기 위해 visited조건식이 들어가 있다. 하지만 같은 좌표에 더 적은 가격으로 들어온 경우에는 예외적으로 다시 방문할 수 있게 해 주었다.

 

 

배운 점

처음에 3차원 배열을 선언하지 않고, 따로 방향값을 만들어서 시도하였다. 이렇게 시도하니 스스로가 헷갈리고 어렵다고 느껴졌다.

그리고 각 방향을 0,1,2,3으로 나누어서 같은지와 처음 시작인지만 검사하면 되는데, 이를 위아래, 오른쪽 왼쪽을 묶어서 생각하다 보니 점점 더 꼬이게 되었다. 다시 생각해 보니, 그저 같은 방향만 체크하는 게 맞다. 후진을 할 일은 없기 때문이다.. 

꾸준히 풀다 보니 500위안에 입성하였다!! 

근데 아직도 모르고 어려운 문제가 많은 것 같다. 더 많은 문제를 풀어봐야 할 것 같다.

순위가 올라가니 알고리즘이 더욱 재미있어지는 것 같다.

더 많이 풀고 잘하는 사람이 되자!