[BOJ] 2665번 : 미로만들기(C++)

김영한·2021년 4월 10일
0

알고리즘

목록 보기
40/74

문제 링크 : 백준 2665번

[문제 접근]

처음에 재귀로 검은방을 흰방으로 바꾸면서 BFS를 돌렸더니 시간초과가 났다.
고민하다가 검은방일때는 cnt를 증가시켜서 가고 흰방일때는 그냥 가는 방식으로 진행했는데 해당 방에 올때 cnt값을 비교하면서 최소값을 계속 갱신시켜주면 (n, n)에는 검은방을 최소 개수만 바꿔서 진행한 결과가 저장된다. (약간 다익스트라 느낌으로?)


알고스팟 문제와 매우 유사한데 다익스트라로 풀면 bigO를 더 단축시킬 수 있을 것 같다.

[소스 코드]

BFS

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
int arr[51][51];
int visit[51][51];
int n;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

void BFS() {
    queue<pair<int, int> > q;
    q.push(make_pair(1, 1));
    memset(visit, 10000, sizeof(visit));
    visit[1][1] = 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(nx<=0 || nx>n || ny<=0 || ny>n) continue;
            
            // arr[nx][ny]가 0일 때는 cnt를 증가시켜야하고 1일때는 증가시키지 말아야한다.
            int tmp = 1-arr[nx][ny];
            
            if(visit[nx][ny] > visit[x][y] + tmp) {
                visit[nx][ny] = visit[x][y] + tmp;
                q.push(make_pair(nx,ny));
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i=1 ; i<=n ; i++) {
        string s;
        cin >> s;
        for(int j=1 ; j<=s.size() ; j++) {
            arr[i][j] = s[j-1] - '0';
        }
    }
    BFS();
    cout << visit[n][n] << "\n";
}

다익스트라

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
int arr[51][51];
int visit[51][51];
int n;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

typedef pair<int, pair<int, int> > p;

void BFS() {
    priority_queue<p, vector<p>, greater<p> > pq;
    pq.push(p(0, make_pair(1, 1)));
    memset(visit, 10000, sizeof(visit));
    visit[1][1] = 0;

    while(!pq.empty()) {
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();

        if(x==n && y==n) return;

        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>n) continue;
            int tmp = 1-arr[nx][ny];
            if(visit[nx][ny] > visit[x][y] + tmp) {
                visit[nx][ny] = visit[x][y] + tmp;
                pq.push(p(visit[nx][ny], make_pair(nx,ny)));
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i=1 ; i<=n ; i++) {
        string s;
        cin >> s;
        for(int j=1 ; j<=s.size() ; j++) {
            arr[i][j] = s[j-1] - '0';
        }
    }
    BFS();
    cout << visit[n][n] << "\n";
}

0개의 댓글