[ BOJ 백준 1261번 - 알고스팟 ] 해설 및 코드

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

 

목적

(1,1)에서 (N,M)으로 가기 위해 거쳐가야 하는 1의 개수의 최소값을 구하자.

 

접근법

1. bfs 알고리즘을 이용하여 최소값을 갱신해 나가자.

 

#include<iostream>
#include<queue>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
char a[101][101];
int m,n,b[101][101],dx[]={1,-1,0,0},dy[]={0,0,1,-1};
struct pos{int x,y;};
 
void go(){
    queue<pos> q;q.push({0,0});
    f(i,0,n)f(j,0,m)b[i][j]=200;b[0][0]=0;
    
    while(!q.empty()){
        int qx=q.front().x,qy=q.front().y;q.pop();
        
        f(d,0,4){
            int x=qx+dx[d],y=qy+dy[d];
            if(x<0||y<0||x>=n||y>=m)continue;
            
            int val=b[qx][qy]+(a[x][y]=='1'?1:0);
            if(b[x][y]>val){
                b[x][y]=val;
                q.push({x,y});
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>m>>n;
    f(i,0,n)cin>>a[i];
    go();
    cout<<b[n-1][m-1];
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.