[백준] 미로만들기 2662번 (c++) bfs, 우선순위 큐

출처 : https://www.acmicpc.net/problem/2665

풀이 방법

먼저 일반적인 bfs알고리즘으로 방문 배열을 visited[y][x][cnt] y, x에서 cnt만큼 검은 방을 뚫고 온 경우로 설정한 후 풀이하였다.

이때 cnt 2501로 설정해 주어야 한다. (50*50) 처음에 51로 설정해서 틀렸다.

 

그 후 다음 좌표의 값이 방문하지 않았고 방이 검은 방인지 흰 방인지에 따라 흰 방이라면 바로 큐에 넣어주고 검은 방이라면 cnt + 1을 해주어서 큐에 넣어주었다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <memory.h>
#include <queue>

using namespace std;
int N, ans = 987654321;
int room[51][51];
int visited[51][51][2501];
int dy[4] = {0, 0, -1, 1};
int dx[4] = {1, -1, 0, 0};

void bfs() {
    queue<pair<int, pair<int, int> > > q; // y, x, 부순 벽의 갯수
    q.push(make_pair(0, make_pair(0, 0)));
    visited[0][0][0] = 1;
    
    while(!q.empty()){        
        int y = q.front().first;
        int x = q.front().second.first;
        int cnt = q.front().second.second;      
        q.pop();
        if (y == N-1 && x == N-1) {
            ans = min(ans, cnt);
            continue;
        }
        for (int i =0;i < 4;i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny >= 0 && ny < N && nx >= 0 && nx < N) {                
                if (room[ny][nx] == 1 && visited[ny][nx][cnt] == 0) { // 빈 방이고 방문x
                    q.push(make_pair(ny, make_pair(nx, cnt)));
                    visited[ny][nx][cnt] = 1;
                }

                if (room[ny][nx] == 0 && visited[ny][nx][cnt+1] == 0){ // 벽이고 방문 x
                    q.push(make_pair(ny, make_pair(nx, cnt + 1)));
                    visited[ny][nx][cnt+1] = 1;
                } 
            }
        }
    }   

}

int main() {

    memset(visited, 0, sizeof(visited));

    cin >> N;    

    for (int i = 0;i < N;i++) {
        string a;
        cin >> a;
        for (int k = 0;k < a.length(); k++) {
            room[i][k] = a[k] - '0';
        }        
    }

    bfs();
    cout << ans;
    return 0;
}

풀이 방법 2

다른 분들의 풀이를 보다보니 우선순위 큐를 사용해서 풀이한 코드를 보고 이를 구현해 보자

 

c++에서 우선순위 큐를 사용하기 위해서는 struct을 사용해 주는 것이 좋다.

구조체의 생성자와 operator의 문법 작성에 유의하자 (const가 있어야 한다.)

우선순위 큐를 사용했기 때문에 제일 처음으로 도착했을 때 cnt값이 정답이 된다.

 

#include <iostream>
#include <vector>
#include <string>
#include <memory.h>
#include <queue>

using namespace std;
int N, ans = 987654321;
int room[51][51];
int visited[51][51][2501];
int dy[4] = {0, 0, -1, 1};
int dx[4] = {1, -1, 0, 0};

struct Record {
    int y;
    int x;
    int cnt;

    Record(int y, int x, int cnt) : y(y), x(x), cnt(cnt) {}
    bool operator< (const Record r) const {
        return cnt > r.cnt; 
    }
};

void bfs() {
    priority_queue<Record> q; // y, x, 부순 벽의 갯수
    q.push(Record(0, 0, 0));
    visited[0][0][0] = 1;
    
    while(!q.empty()){                
        Record nRecord = q.top();
        int y = nRecord.y;
        int x = nRecord.x;
        int cnt = nRecord.cnt; 
        q.pop();
        if (y == N-1 && x == N-1) {
            ans = cnt;
            return ;
        }
        for (int i =0;i < 4;i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny >= 0 && ny < N && nx >= 0 && nx < N) {                
                if (room[ny][nx] == 1 && visited[ny][nx][cnt] == 0) { // 빈 방이고 방문x
                    q.push(Record(ny, nx, cnt));
                    visited[ny][nx][cnt] = 1;
                }

                if (room[ny][nx] == 0 && visited[ny][nx][cnt+1] == 0){ // 벽이고 방문 x
                    q.push(Record(ny, nx, cnt+1));
                    visited[ny][nx][cnt+1] = 1;
                } 
            }
        }
    }   

}

int main() {

    memset(visited, 0, sizeof(visited));

    cin >> N;    

    for (int i = 0;i < N;i++) {
        string a;
        cin >> a;
        for (int k = 0;k < a.length(); k++) {
            room[i][k] = a[k] - '0';
        }        
    }

    bfs();
    cout << ans;
    return 0;
}