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

김개발·2021년 6월 4일

cpp level3 알고리즘 프로그래머스

프로그래머스

목록 보기

33/42

문제 푼 날짜 : 2021-06-04

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67259

접근 및 풀이

문제를 다 읽자마자 DFS, BFS를 떠올렸다.
경주로를 건설해나가면서 직진과 방향을 바꾸는 경우만 잘 체크해주면 된다고 생각했다. 이 조건을 고려해주는 것 외에는 일반적인 DFS, BFS 문제라고 생각해서 쉬울거라 얕봤는데, 구현하는데 꽤나 애를 먹었다.

(0, 0) 에서 (N - 1, N - 1)까지 상하좌우 조건을 체크하면서 움직여 직진하는 경우, 방향을 바꾸는 경우의 수를 카운트해서 마지막에 도달했을 때 최소 비용을 갱신하는 식으로 구현하려고 했다. 이를 익숙한 DFS로 구현했는데, 시간초과가 떴다. 재방문 조건 설정과 비용 계산하는 방법을 잘못 접근한 것 같다.

이리저리 수정을 거치다가 포기하고 BFS로 풀었다. 실제로 테스트 중이었다면 못 고치고 멘붕이 와서 틀렸을 것 같다...
BFS를 이용할 때는 마찬가지로 (0, 0) 에서 (N - 1, N - 1)까지 조건을 체크하면서 움직여주었고, 움직이면서 주어진 board 각각 자리까지의 최솟값을 갱신하는 식으로 구현하였다.

코드

DFS (시간초과)

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> c_board;
bool visited[26][26] = { false, };
int N, ret = 987654321;
int dy[4] = { 1, -1,  0, 0 };
int dx[4] = { 0,  0, -1, 1 };

void DFS(int y, int x, int go, int turn, int dir) {  
    if (y == N - 1 && x == N - 1) {
        int price = (go * 100) + (turn * 500);
        ret = min(ret, price);
        return;
    }

    for (int i = 0; i < 4; i++) {
        bool flag = false;
        int nextY = y + dy[i];
        int nextX = x + dx[i];
        
        if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N) continue;
        if (visited[nextY][nextX] || c_board[nextY][nextX] == 1) continue;  
        
        if ((y != 0 || x != 0) && dir != i) flag = true;
        
        visited[nextY][nextX] = true;
        if (flag) { // 코너 생성
            DFS(nextY, nextX, go + 1, turn + 1, i);
        } else { // 그대로 직진
            DFS(nextY, nextX, go + 1, turn, i); 
        }
        visited[nextY][nextX] = false;
    }
    return;
}

int solution(vector<vector<int>> board) {
    int answer = 0;
    c_board = board;
    N = board.size();
    
    visited[0][0] = true;
    DFS(0, 0, 0, 0, 0);
    
    answer = ret;
    return answer;
}

BFS

#include <string>
#include <vector>
#include <queue>

using namespace std;

struct CAR {
    int y, x, dir, cost;
};

int solution(vector<vector<int>> board) {
    int answer = 987654321, N = board.size();
    int dy[4] = { 0,  0, 1, -1 };
    int dx[4] = { 1, -1, 0,  0 };
    queue<CAR> q;
    
    q.push({ 0, 0, 4, 0 }); // (0, 0)에서의 방향은 임의의 방향(4)라고 설정
    
    while (!q.empty()) {
        CAR c = q.front();
        q.pop();
        
        if (c.y == N - 1 && c.x == N - 1) { // 도착했을 경우
            answer = min(answer, c.cost);
            continue;
        }
        
        for (int i = 0; i < 4; i++) {
            int nextY = c.y + dy[i];
            int nextX = c.x + dx[i];
            if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N || board[nextY][nextX] == 1) continue;
            
            int now_cost = 0;
            if (c.dir == 4 || c.dir == i) now_cost = c.cost + 100; // 첫 스타트 또는 그대로 직진할 경우
            else now_cost = c.cost + 600; // 방향을 바꿀 경우
            
            if (board[nextY][nextX] == 0 || board[nextY][nextX] >= now_cost) { // 방문하지 않았거나 cost가 작거나 같을 경우
                q.push({ nextY, nextX, i, now_cost });
                board[nextY][nextX] = now_cost;
            }
        }
    }
    return answer;
}