[Dijkstra] 1261번 알고스팟

1261번 알고스팟

 

https://www.acmicpc.net/problem/1261

 

문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 NM 크기이며, 총 11크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1을 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

 

출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

 

예제 입력

3 3
011
111
110

4 2
0001
1000

6 6
001111
010000
001111
110001
011010
100010

 

예제 출력

3

0

2

 

해결방법

백준 강의를 참고하였다

처음에는 DFS로 모든 벽을 부수고 BFS로 탐색하는 경우를 구현해봤지만 ⏱시간 초과가 발생하였다

다른 접근 방법을 찾아야했다

 

⭐️솔루션⭐️

이 문제에서는 단계적 BFS 를 적용해야했다

단계적 BFS란 queue 와 next_queue 를 통해 단계적으로 탐색을 진행하는 것이다

• 먼저 queue에 시작점을 (0,0) 넣는다
• 4방향 탐색을 진행하며 0인경우 BFS 탐색을 진행한다
• 만약 1을 만나면 이는 부술수 있는 첫번째 벽인 셈이다. 따라서 next_queue에 넣어준다
• queue의 BFS 탐색이 끝났다면 queue는 비어있는 상태이고, next_queue는 첫번째 BFS 탐색 도중 만난 벽의 위치가 들어있을 것이다
• 이제 next_queue에 있는 위치들을 queue로 넣어주고 next_queue는 다시 clear 해준다
• 이제 queue는 벽의 위치를 가지고있다. 이 벽의 위치에서 0인 것을 BFS 탐색한다면 첫번째 벽들을 부쉈을 때, 갈 수 있는 0까지 탐색할 것이다
• 마찬가지로 1을 만난다면 다시 next_queue에 넣어준다
• 만약 전부 탐색했다면 next_queue에는 아무 값도 넣어지지 않으며, queue 또한 빈상태가 되므로 while문이 종료된다

 

하지만 테스트케이스에 답은 나오지만 결과는 '틀렸습니다' 가 나왔다...흑

 

 

⭐️다익스트라 알고리즘(Dijkstra Algorithm)⭐️

결과가 나오지 않아서 블로그를 뒤지던 중, 본 문제를 다익스트라 알고리즘으로 푸는법을 찾았다

다익스트라 알고리즘은 그래프에서 n개의 정점이 있고 m개의 간선이 주어지는 경우 간선 간의 가중치가 비용인 경우가 주어진다. 이 때, 가중치의 값을 최소화하여 정점간의 이동을 해야한다

 

하지만 이 경우는 그래프가 아닌 2차원 행렬이다. 또한 가중치 또한 제시되어있지 않다

본 문제는 정점간이 아닌 행렬의 각 칸마다 이동을 하고, 벽을 부수는 것이 비용인 것이다

 

일단 2차원 배열 2개를 준비한다

map[MAX][MAX]		// 빈 방 또는 벽으로 이루어진 미로 배열
dist[MAX][MAX]		// 최소 비용을 저장하는 배열, 초기값은 INF

시작점 (0,0) 부터 탐색을 시작한다. 시작점의 dist 값은 0이다.

상,하,좌,우 인접한 4개의 노드를 탐색한다.

만약 인접 노드가 '0' 인 경우는 빈 방이기 때문에 비용이 발생하지 않는다

하지만 인접 노드가 '1' 인 경우는 벽이기 때문에 +1 의 비용이 발생한다

 

여기서 한가지 이슈가 발생할 수 있다고 생각했다

"한 노드를 중복 탐색하면 값이 증가하지 않나??"

하지만 Relax 연산으로 인해 최단경로가 이미 저장되어있기 때문에 조건문으로 해결이 가능하다

 

⭐️입출력 이슈⭐️

1개의 정수를 입력받기 위해 아래의 방법을 사용했다

scanf("%1d",&map[i][j]);

 

하지만!!!!

sync_with_stdio(false) 를 한 이후에는 C++의 입출력과 C의 입출력을 섞어 쓰면 안 됩니다.

라는 새로운 사실을 알게되었다...!!!!!

 

소스코드

[ 단계적 BFS ]

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 100
#define INF 987654321
using namespace std;

int n,m;
int map[MAX][MAX];
int dist[MAX][MAX];

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

bool is_possible(int row,int col){
    if(row<0 || row>=n || col<0 || col>=m) return false;
    return true;
}

void bfs(){
    queue<pair<int, int>> q;
    queue<pair<int, int>> next_q;
    
    q.push(make_pair(0, 0));
    dist[0][0] = 0;
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(is_possible(nx, ny)){
                if(dist[nx][ny] == -1){
                    if(map[nx][ny] == 0){
                        dist[nx][ny] = dist[x][y];
                        q.push(make_pair(nx, ny));
                    }else{
                        dist[nx][ny] = dist[x][y] + 1;
                        next_q.push(make_pair(nx, ny));
                    }
                }
            }
        }
        
        if(q.empty()){
            swap(q, next_q);	// q와 next_q 교환
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> m >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%1d",&map[i][j]);
            dist[i][j] = -1;
        }
    }
    
    bfs();
    cout << dist[n-1][m-1] << endl;
    
    return 0;
}

 

[ 다익스트라 알고리즘 ]

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 101
#define INF 987654321
using namespace std;

struct node {
    int x,y,dist;
    
    node(int _x,int _y,int _dist) : x(_x),y(_y),dist(_dist) {}
    
    bool operator > (const node& n) const {
        return dist > n.dist;
    }
};

int n,m;

int map[MAX][MAX];
int dist[MAX][MAX];

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

void dijkstra(){
    priority_queue<node,vector<node>,greater<node>> pq;
    pq.push(node(0,0,0));
    dist[0][0] = 0;
    
    while(!pq.empty()){
        int x = pq.top().x;
        int y = pq.top().y;
        int d = pq.top().dist;
        pq.pop();
        
        if(x==n-1 && y==m-1) break;
        
        if(d > dist[x][y]) continue;
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
            
            // Relax 연산
            if(dist[nx][ny] > dist[x][y] + map[nx][ny]){
                dist[nx][ny] = dist[x][y] + map[nx][ny];
                pq.push(node(nx,ny,dist[nx][ny]));
            }
        }
    }
    
    printf("%d\n",dist[n-1][m-1]);
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL); cout.tie(NULL);
    
    scanf("%d %d",&m,&n);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%1d",&map[i][j]);
            dist[i][j] = INF;
        }
    }
    
    dijkstra();
}