[도전 21일차] 통나무 옮기기 - KOI 고등부 풀이

※복습 : 

 

문제 : BOJ 1938 통나무 옮기기

문제 링크

 

사용 알고리즘 : BFS

 

풀이:

최단 횟수를 구하는 문제는 대부분 무가중치 그래프에서의 최단 거리 문제로 변형되고, 이는 BFS로 해결 가능하다. 앞서 풀었던 미로만들기 문제 와 비슷하다. 

입력은 공백으로 구분되어 입력되므로 scanf(" %c",&chr); 과 같이 입력 받아 처리해주면 된다.

통나무의 세 점을 모두 들고 다니는 것은 번거로우므로 중심점과 방향(가로/세로)으로 구조화 하자. 입력 받을 때 배열에 'B' ,'C' 인 경우 따로 표시를 해두어, 각각 2번째로 찾은 위치가 통나무의 중심 좌표다.  

탐색을 진행할 때 세 점이 모두 맵 안에 들어 있는지 확인을 해주어야 한다. 이것은 safe 함수를 개량하여 간단하게 코드를 짤 수 있다.

 

safe(a,b,dir) {

if(dir==0) //가로

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

else //세로

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

}

코드

#include<stdio.h>
#include<queue>
using namespace std;
int n,arr[60][60],v[60][60][2],cnt1,cnt2;
int dr[4]={1,0,-1,0},dc[4]={0,1,0,-1};
struct wood{
    int r,c,dir;
};
struct wood s,e;
inline bool safe(int a,int b,int dir) {
    if(dir==0) //가로
        return a>=0 && a<n && b>=1 && b<n-1 && arr[a][b]<=0 && arr[a][b-1]<=0 && arr[a][b+1]<=0;
    else        //세로
        return a>=1 && a<n-1 && b>=0 && b<n && arr[a][b]<=0 && arr[a-1][b]<=0 && arr[a+1][b]<=0;
}
void input(){
    scanf("%d",&n);
    char c;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            scanf(" %c",&c);
            if(c=='0'||c=='1')
                arr[i][j]=c-'0';
            else if(c=='B'){
                arr[i][j]=-1;
                if(++cnt1==2){
                    if(safe(i,j,0)&&arr[i][j-1]==-1)
                        s={i,j,0};
                    else
                        s={i,j,1};
                }
            }
            else if(c=='E'){
                arr[i][j]=-2;
                if(++cnt2==2){
                    if(safe(i,j,0)&&arr[i][j-1]==-2)
                        e={i,j,0};
                    else
                        e={i,j,1};
                }
            }
        }
}
int bfs(wood& s,wood& e){
    queue<wood> q;
    q.push(s); v[s.r][s.c][s.dir]=0; 
    while(!q.empty()){
        wood x=q.front(); q.pop();
        int d=v[x.r][x.c][x.dir];
        for(int i=0;i<4;i++){
            int r=x.r+dr[i],c=x.c+dc[i];
            if(safe(r,c,x.dir) && !v[r][c][x.dir]){
                q.push({r,c,x.dir});
                v[r][c][x.dir]=d+1;
            }
        }
        if(safe(x.r+1,x.c,0)&&safe(x.r,x.c,0)&&safe(x.r-1,x.c,0)&&!v[x.r][x.c][!x.dir]){
            q.push({x.r,x.c,!x.dir});
            v[x.r][x.c][!x.dir]=d+1;
        }
    }
    return v[e.r][e.c][e.dir];
}
int main(){
    input();
    printf("%d",bfs(s,e));
}

 

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