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

문제 설명

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

문제 풀이

• 간단한 BFS로 문제였다.
• BFS로 진행하되 방문체크는 chk[x][y][들어온 방향]으로 수행한다.
• 들어온 방향에 따라 다음 3가지 케이스로 나누어 진행한다.
  - 들어온 방향과 정반대 방향으로 가는 경우 -> 진행X
  - 들어온 방향과 같은 방향으로 가는 경우 -> 100원 더해줌
  - 들어온 방향과 수직 방향으로 가는 경우 -> 100 + 500원 더해줌

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int N, INF = 987654321;
    public int[] dx = {0, 1, 0, -1};
    public int[] dy = {1, 0, -1, 0};

    public int calDir(int d) {
        return d > 3 ? d - 4 : d;
    }

    public class Point {
        int x, y, d, c;

        public Point(int x, int y, int d, int c) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.c = c;
        }
    }

    public int solution(int[][] board) {
        //초기화
        N = board.length;
        int[][][] chk = new int[N][N][4];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                Arrays.fill(chk[i][j], INF);
        Queue<Point> q = new ArrayDeque<>();
        q.add(new Point(0,0,0, 0));
        q.add(new Point(0,0,1, 0));
        q.add(new Point(0,0,2, 0));
        q.add(new Point(0,0,3, 0));
        chk[0][0][0] = 0;
        chk[0][0][1] = 0;
        chk[0][0][2] = 0;
        chk[0][0][3] = 0;

        while(!q.isEmpty()) {
            Point cur = q.poll();
            for (int d = 0; d < 4; d++) {
                int X = cur.x + dx[d];
                int Y = cur.y + dy[d];
                if (X < 0 || Y < 0 || X >= N || Y >= N || board[X][Y] == 1) continue;
                //왔던 방향 일 떄
                if (cur.d == calDir(d + 2)) continue;
                int cost;
                //직선 거리 일 때
                if (cur.d == d) cost = cur.c + 100;
                //수직 거리 일 때
                else cost = cur.c + 600;
                if (chk[X][Y][d] <= cost) continue;
                chk[X][Y][d] = cost;
                q.add(new Point(X, Y, d, cost));
            }
        }

        int result = Integer.MAX_VALUE;
        for (int i = 0; i < 4; i++)
            result = Math.min(result, chk[N-1][N-1][i]);
        return result;
    }
}