[ BOJ 백준 1981번 - 배열에서 이동 ] 해설 및 코드

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

 

목적

아래와 같은 nxn 배열의 (0,0) 부터 (n-1,n-1)까지 이동하기 위해 거쳐간 수들의 최대값과 최소값의 차이를 가장 작게 만드는 경우를 찾자.

접근법

1. 투 포인터 알고리즘으로 최소 최대 값을 정한 후, BFS 알고리즘을 이용해 최소,최대의 범위 안에서 이동 가능한지 검사한다. (투 포인터 알고리즘 설명 참고 : 백준 2842 - 집배원 한상덕)

 

#include<iostream>
#include<cstring>
#include<algorithm>
#define REP(i,n) for(int i=0;i<n;++i)
using namespace std;
 
int n,a[101][101],mn,mx,z[101][101],di[]={0,0,1,-1},dj[]={1,-1,0,0};
 
bool dfs(int i,int j){
    if(i==n-1&&j==n-1)return true;
    z[i][j]=1;
    REP(d,4){
        int r=i+di[d],c=j+dj[d];
        if(r<0||c<0||r>=n||c>=n||z[r][c]||a[r][c]<mn||a[r][c]>mx)continue;
        if(dfs(r,c))return true;
    }
    return false;
}
 
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    
    mn=200;mx=0;
    cin>>n;
    REP(i,n)REP(j,n){
        cin>>a[i][j];
        mn=min(mn,a[i][j]);
        mx=max(mx,a[i][j]);
    }
    
    int result=mx-mn,until=mx;
    mx=a[0][0];
    while(mn<=a[0][0]&&mx<=until){
        memset(z,0,sizeof(z));
        if(dfs(0,0)){
            result=min(result,mx-mn);
            mn++;
        }else mx++;
    }
    cout<<result;
}
 

 

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

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