[백준][C++] 2665 미로만들기

www.acmicpc.net/problem/2665

2665번: 미로만들기

 

 

알고리즘 종류

    - 최단거리

    - DP

 

 

 

사고 과정

    - cost 2차원 배열을 좌측상단에서 BFS로 이동하면서 최소 비용만 저장한다. 저장하면 queue에 넣어서 계속 BFS를 수행한다. 이렇게 cost 2차원 배열에는 최소 비용만 기록된다.

 

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int n;
 
int mat[51][51];
int cost[51][51];
 
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
 
 
bool isValid(int y, int x){
    return (x>=1 && x <=n) && (y>=1 && y<=n);
}
 
 
void solution(){
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cost[i][j] = 987654321;
        }
    }
    
    queue<pair<int,int> > q;
    q.push({1,1});
    cost[1][1] = 0;
    
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        int c = cost[y][x];
        q.pop();
        
        for(int d=0; d<4; d++){
            int ny = y + dir[d][0];
            int nx = x + dir[d][1];
            
            if(!isValid(ny, nx)) continue;
            
            if(mat[ny][nx] == 1){
                if(cost[ny][nx] > c){
                    cost[ny][nx] = c;
                    q.push({ny, nx});
                }
            }
            else {
                if(cost[ny][nx] > c + 1){
                    cost[ny][nx] = c + 1;
                    q.push({ny, nx});
                }
            }
        }
    }
    
    cout << cost[n][n];
}
 
 
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    scanf("%d", &n);
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            scanf("%1d", &mat[i][j]);
        }
    }
    solution();
}
 
 
 

 

 

 

시행착오

    - 알고리즘 분류로 문제를 풀고 있다. 이번 문제의 분류는 다익스트라였다. 그래서 어떻게든 다익스트라로 풀기 위한 전략을 세웠다. 미로에서 상하좌우 1로 이루어진 공간들에 번호를 매긴다. 마치 node를 만들는 것과 같다. 그리고 각 번호가 매겨진 곳에서 다시 BFS를 수행하여 간선의 비용을 얻는다. 이렇게 얻으면 다익스트라를 수행할 수 있다. 그런데 하다보니 쓸데없이 복잡해졌다. 나의 전략의 문제점은 다음과 같다.

        1. 1로 연결된 공간에 번호를 매겨서 노드를 만들 필요가 없다. 다익스트라의 핵심은 DP이다. 최단거리만 저장하는 것이다. 그것의 소재가 단지 node일 뿐이다. 그래서 굳이 node를 만들어 줄 필요 없이 mat[i][j]에서 다른 곳을 이동할 때 최소 비용으로 갱신해주면 된다.