[코딩테스트 C++] 알고스팟

오늘의 문제

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

알고스팟

접근 방식

• 그래프에 우선순위큐가 접목된것은 처음 풀어본다.
• 다른문제같은 경우는 아예 1인곳은 못 가곤 했는데, 이 문제에서는 벽을 부수고 갈 수 있다.
• 벽을 부수는 것을 최소화하라했으니, queue에 넣어 bfs로 풀되, 벽을 적게 부순 경우를 먼저 다음으로 수행한다.
• 이게 가능한 이유는 가장 적은 벽을 부순 경우의 다음 경우가 반드시 다른 경우보다 작을 것이라는것이 확실하기 때문.
• 어떻게보니, 그리디, 우선순위큐, 그래프(bfs) 가 섞여있다. 재미있는 문제였다.

나의 풀이

#include <iostream>
#include <vector>
#include <queue>
#pragma warning(disable: 4996)
using namespace std;

const int MAX = 100;
int n, m;
int ar[MAX][MAX];
bool visit[MAX][MAX] = {false, };
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};

int bfs(){
    int answer = 0;
    priority_queue<pair<int, pair<int, int>>,
        vector<pair<int, pair<int, int>>>,
        greater<pair<int, pair<int, int>>>> q;
    q.push(make_pair(0,make_pair(0, 0)));
    visit[0][0] = true;
    while(!q.empty()){
        int a = q.top().second.first;
        int b = q.top().second.second;
        q.pop();
        for(int i=0;i<4;i++){
            int ma = a + dx[i];
            int mb = b + dy[i];
            if(ma >= n || ma <0 || mb >= m || mb <0)
                continue;
            if(visit[ma][mb] == false){
                ar[ma][mb] += ar[a][b];
                visit[ma][mb] = true;
                q.push(make_pair(ar[ma][mb],make_pair(ma, mb)));
                if(ma == n-1 && mb == m-1)
                    return ar[ma][mb];
            }
        }
    }
    return answer;
}

다른 풀이

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

int main()
{
    int N, M;
    scanf("%d%d",&M,&N);
    char A[N][M];
    int D[N][M], dr[4]={1,0,-1,0}, dc[4]={0,1,0,-1};

    for( int i=0; i<N; i++ ){
        scanf("%s",A[i]);
        for( int j=0; j<M; j++ ) D[i][j] = 1000000000;
    }

    D[0][0]=0;
    priority_queue<pair<int,pair<int,int> > > q;
    q.push({0,{0,0}});
    
    while( !q.empty() ){
        int r = q.top().second.first, c = q.top().second.second, sum = -q.top().first;
        q.pop();
        if( D[r][c] < sum ) continue;
        for( int k=0; k<4; k++ ){
            int i=r+dr[k], j=c+dc[k], dist=sum;
            if( i<0 || j<0 || i>=N || j>=M ) continue;
            if( A[i][j]=='1' ) dist++;
            if( D[i][j] <= dist ) continue;
            D[i][j] = dist;
            q.push({-dist,{i,j}}); 
        }
    }
    printf("%d",D[N-1][M-1]);
    return 0;
}

배울 점

• 이분은 마지막에 도달한 경우에서 멈추지 ㅇ낳는다. 멈춰야할것같다.