[도전 20일차] 미로 만들기 풀이 - KOI 고등부

※복습 : 

 

문제 : 백준 2665 미로 만들기

문제 링크

 

사용 알고리즘 : BFS

 

풀이:

시작점에서부터 도착점까지 가면서 색을 바꾸어야 할 검은 방의 최소 개수를 구하는 것이 목표다.   시작점으로부터 탐색을 돌리는데 들고 다닐 것은 지금까지 바꾼 검은 방의 개수다. visited 배열에 바꾼 검은 방 개수를 저장하면서 만약 개수가 작으면 갱신하고, 크거나 같으면 무시하면 된다. 이떄 DFS, BFS 모두 가능하다.

 

safe 함수를 써서 인덱스가 맞는 지 확인하는 것이 은근 편하다. 참고하자.

 

bool safe(int a,int b){

	return a>=0&&a<n&&b>=0&&b<n;

}

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
const int INF = 1e9;
using namespace std;
int n,arr[51][51],v[51][51],dr[4]={1,0,-1,0},dc[4]={0,1,0,-1};
inline bool safe(int a,int b){
    return a>=0&&a<n&&b>=0&&b<n;
}
void bfs(int s1,int s2){
    queue<tuple<int,int,int>> q;
    q.push(make_tuple(s1,s2,0));
    while(!q.empty()){
        int x,y,d;
        tie(x,y,d)=q.front(); q.pop();
        for(int i=0;i<4;i++){
            int r=x+dr[i],c=y+dc[i];
            if(!safe(r,c)) continue;
            d+=!arr[r][c];
            if(d<v[r][c]){
                v[r][c]=d;
                q.push(make_tuple(r,c,d));
            }
            d-=!arr[r][c];
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            scanf("%1d",&arr[i][j]);
            v[i][j]=INF;
        }
    bfs(0,0);
    printf("%d",v[n-1][n-1]);
}

 

궁금한 점이 있으시다면 질문 남겨주세요 :)