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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

일반적인 BFS 알고리즘을 사용해서 목적지까지 가는 경우를 구할 수 있다. 하지만 이 문제에서는 목적지까지 사용되는 최소 금액을 구해야 한다. 문제를 읽어보면 직선 도로 하나 만들 때는 100원, 코너를 하나 만들 때는 500원이 든다. 이 말은 (x, y) 좌표가 있다고 생각했을 때, (x, y)에 도달하기 전 블록에서의 방향과 (x, y)에서 다음 지점으로 나아갈 방향이 같은지 다른지가 금액을 결정한다는 말이다. 그리고 그 말은 한 지금 (x, y)까지 도달하는데 필요한 금액이 (x, y) 지점에 도달했을 때의 방향마다 다르다는 말이다. 따라서 3차원 배열을 생성해서 BFS 알고리즘을 구현하면 해결할 수 있다.

코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct pos {
    int x, y, dir;
};

// (j, i) 에서의 최소값을 담을 배열
int chk[25][25][4];
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };

int bfs(const vector<vector<int>>& board, const int n) {
    queue<pos> q;
    for (int i = 0; i < 4; i++) {
        q.push({ 0, 0, i });
        chk[0][0][i] = 0;
    }

    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int d = q.front().dir;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i]; int ny = y + dy[i];
            if (nx < 0 || nx > n - 1 || ny < 0 || ny > n - 1) continue;
            if (board[ny][nx] == 1) continue;
            // 직선 도로를 만들 때
            if (d == i) {
                // 아직 방문한 적 없는 지점이거나 최솟값을 갱신할 수 있을 때
                if (chk[ny][nx][d] == -1 || chk[ny][nx][d] > chk[y][x][d] + 100) {
                    chk[ny][nx][d] = chk[y][x][d] + 100;
                    q.push({ nx, ny, d });
                }
            }
            // 코너를 만들 때
            else {
                // 아직 방문한 적 없는 지점이거나 최솟값을 갱신할 수 있을 때
                if (chk[ny][nx][i] == -1 || chk[ny][nx][i] > chk[y][x][d] + 600) {
                    chk[ny][nx][i] = chk[y][x][d] + 600;
                    q.push({ nx, ny, i });
                }
            }
        }
    }
    int ans = 987654321;
   // 목적지의 네 방향을 확인했을 때 최솟값이 정답이 된다
    for (int i = 0; i < 4; i++) {
        if (chk[n - 1][n - 1][i] == -1) continue;
        ans = min(ans, chk[n - 1][n - 1][i]);
    }
    return ans;
}

int solution(vector<vector<int>> board) {
    int size = board.size();
    // 방문하지 않는 곳을 확인하기 위해 -1로 초기화
    for (int i = 0; i < size; i++)
        for (int j = 0; j < size; j++)
            for (int l = 0; l < 4; l++)
                chk[i][j][l] = -1;

    int answer = bfs(board, size);
    return answer;
}