프로그래머스 - 경주로 건설

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

프로그래머스

 

1. 특징

• bfs

 

2. 구현 방법

• 기본적인 bfs의 이차원 dist[][]를 3차원 cost[][][] (x, y, 방향)으로 나타냄
• cost를 INT_MAX로 초기화
• bfs를 돌면서, 다음(nx, ny)으로의 방향과 현재(curx, cury3)로의 방향을 비교하면서 cost 배열을 갱신함

3. 코드

#include <bits/stdc++.h>

using namespace std;

int cost[27][27][3]; //cost(x, y, 방향) = 가격
int dx[4] = {0, 0, -1, 1}; 
int dy[4] = {-1, 1, 0, 0};

int solution(vector<vector<int>> board) {
    int answer = 0;
    int n = board.size();
    
    fill(&cost[0][0][0], &cost[26][26][2], INT_MAX);
    
    queue<tuple<int, int, int>> q; // x y 방향(수평: 0, 수직: 1)
    q.push(make_tuple(0, 0, -1));  //맨처음에는 방향이 없기 때문에 방향을 -1로 설정
    cost[0][0][0] = 0; cost[0][0][1] = 0; 
    
    while(!q.empty())
    {
        
        int curx, cury, curdir;
        tie(curx, cury, curdir) = q.front(); 
        q.pop();
        
        for(int dir = 0; dir < 4; dir++) //좌, 우, 위, 아래
        {
            int nx = curx + dx[dir];
            int ny = cury + dy[dir];
            int ndir = -1;
            if(dir == 0 || dir == 1) ndir = 0; //ndir = 1
            if(dir == 2 || dir == 3) ndir = 1;
            
            
            if(nx < 0 || nx > n-1 || ny < 0 || ny > n-1) continue;
            if(board[nx][ny] == 1) continue;
            int newcost = -1;
            //다음으로 갈 곳의 방향과 이전 방향이 같으면 혹은 맨처음 시작이면(curx == 0 && cury == 0)
            if((ndir == 0 && curdir == 0) || (ndir == 1 && curdir == 1) || curdir == -1) 
            {
                newcost = cost[curx][cury][ndir] + 100;
            }
            //다음으로 갈 곳의 방향과 이전 방향이 다르면
            if((ndir == 0 && curdir == 1) || (ndir == 1 && curdir == 0))
            {
                newcost = cost[curx][cury][curdir] + 100 + 500;
            }
            //새로운 곳으로 가는 가격이 그곳에 있던 기존 값보다 크면 continue;
            if(newcost > cost[nx][ny][ndir]) continue;
            cost[nx][ny][ndir] = newcost;
            q.push(make_tuple(nx, ny, ndir));
         }
        
    }
    
    // for(int i = 0; i < n; i++)
    // {
    //     for(int j = 0; j < n; j++)
    //     {
    //         cout << min(cost[i][j][0], cost[i][j][1]) << ' ';
    //     }
    //     cout << endl;
    // }
    answer = min(cost[n-1][n-1][0], cost[n-1][n-1][1]);
    
    return answer;
}