[백준][C++] 1261 알고스팟

 

 

 

알고리즘 종류

    - 다익스트라

 

 

 

사고 과정

    - 출발지점에서 목표지점까지의 모든 경로들 중에서 벽의 개수가 가장 적은 경로를 선택하면 될 것 같았다.

    - 출발지점이 하나이므로 다익스트라를 사용해보자.

    - 경로에 있는 벽의 개수는 어떻게 기록할까? 다익스트라는 최소비용을 기록했는데, 여기서는 벽의 개수를 비용이라고 생각하면 최소 벽의 개수를 dist라는 배열에 기록하면 될 것 같다.

 

 

 

구현(C++)

#include <iostream>
#include <stdio.h>
#include <queue>
 
using namespace std;
 
int r, c;
 
int graph[101][101];
int dist[101][101];
int isVisited[101][101];
 
int d[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
 
 
bool isValid(int y, int x){
    return (y>=0 && y<r) && (x>=0 && x<c);
}
 
 
void dijkstra(){
    
    queue<pair<int, int> > q;
    isVisited[0][0] = 1;
    dist[0][0] = 0;
    q.push({0,0});
    
    while(!q.empty()){
        
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int ny = y + d[i][0];
            int nx = x + d[i][1];
            
            if(isVisited[ny][nx]) continue;
            if(!isValid(ny, nx)) continue;
            
            // 가는 곳에 벽이 있으면, '가는 곳에 이전에 기록된 최소 비용' vs '가는 곳에 벽을 포함한 비용'
            if(graph[ny][nx] == 1){
                // 기록된 최소 비용보다 새로운 비용이 더 작다면, 값을 갱신
                if(dist[ny][nx] > dist[y][x] + 1){
                    dist[ny][nx] = dist[y][x] + 1;
                    q.push({ny, nx});
                }
            // 가는 곳에 벽이 없으면, '가는 곳에 이전에 기록된 최소 비용' vs '가는 곳에 벽 없이 가는 비용'
            } else {
                // 기뢱된 최소 비용보다 새로운 비용이 더 작다면, 값을 갱신
                if(dist[ny][nx] > dist[y][x]){
                    dist[ny][nx] = dist[y][x];
                    q.push({ny, nx});
                }
            }
            
        }
    }
}
 
 
 
 
int main(void){
    
    cin >> c >> r;
    
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            scanf("%1d", &graph[i][j]);
            dist[i][j] = 987654321;
        }
    }
    
    dijkstra();
    
    // 결국, 마지막에 기록된 값은 가장 최소 비용만 기록된다.
    cout << dist[r-1][c-1] << endl;
}
 
 
 
 

 

 

 

시행착오

    - 다익스트라는 이전의 최소 비용과 비교하면서 값을 갱신하기 때문에 DP의 일종이다. 이 사실을 다시 되새긴다.

    - 한 지점에서 다른 모든 지점으로 가는 최소 비용을 구하는 방법이 다익스트라이다.