백준 1981 배열에서 이동

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

문제 설명

상하좌우로 이동이 가능한 배열이 있다

왼쪽 상단에서 시작하여 오른쪽 하단까지 오면서 몇개의 수를 거쳐 오게 됨.
이들중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구한다.

예시)

위의 경로로 이동한다면 최댓값이 2, 최솟값이 0으로 둘의 차가 2이므로 (최대 - 최소) 가 가장 작아진다

코드 해석

1. map을 입력받으면서 값의 최대와 최소를 Max, Min 전역변수에 저장

    for(int i=0;i<num;i++){
		for(int j=0;j<num;j++){
			scanf("%d",&arr[i][j]);
			
			if(arr[i][j]>Max){
				Max = arr[i][j];
			}
			if(arr[i][j]<Min){
				Min = arr[i][j];
			}
		}
			
	}

2. 이분탐색을 통해 가능한 가장 작은 차이를 구한다

   start 값은 0, end 값은 Max로 설정( 최대 최소의 차이가 Max보 다 클 수는 없음)

int start = 0;
	int end = Max;
	while(start<=end){
		int mid = (start+end)/2;
		
		if(check(mid)){ // 성공 
			end = mid-1;
		}else{ // 실패 
			start = mid +1;
		}
	}
	printf("%d",start);

3. 이분탐색의 mid 값 가능한지 확인하는 함수..

   우선 mid 값이 인자로 들어옴
   mid 값은 (최댓값 - 최솟값)
   map에서 돌면서 최대 - 최소가 mid보다 작은지 확인해야 한다.

   최대 - 최소 값만 가정하고 통과가 가능한지 확인이 불가능하다...

   -> 최대, 최소값을 고정시켜줘야함..!

   ---

   Min부터 Max까지의 for문을 통해 수 i를 뽑는다
   최솟값은 i, 최댓값은 i+mid라 가정하고 map을 돌면서 i ~ i+mid 사이의 값으로 (n,n)까지 올 수 있는지 확인한다

   한마디로 최대-최소값인 mid가 주어졌을 때
   mid를 간격으로 하는 가능한 모든 최대, 최소값을 고정한 다음 전부 queue로 돌려준다

   int check(int mid){ // mid는 최솟값과 최대값의 차이  
   	
   	
   	for(int i=Min;i<=Max;i++){ // min부터 Max 사이의 mid 만큼의 간격 i ~ i+mid 
   		if(arr[0][0]<i || arr[0][0]>mid+i){
   			continue;
   		}
   		queue<pair<int,int> > q;
   		memset(visit, 0, sizeof(visit));
   		q.push(make_pair(0,0));
   		visit[0][0]=1;
   		while(!q.empty()){
   			if(q.front().first == num-1 && q.front().second == num-1){
   				return 1;
   			}
   			for(int j=0;j<4;j++){
   				int xx = q.front().first + _x[j];
   				int yy = q.front().second +_y[j];
   				
   				if(xx>=0&&xx<num&&yy>=0&&yy<num&&visit[xx][yy]==0){
   					if(arr[xx][yy]>=i && arr[xx][yy]<=mid+i){
   						q.push(make_pair(xx,yy));
   						visit[xx][yy]=1;
   					}
   					
   				}
   			}
   			q.pop();
   		}
   	}
   	return 0;
   }
   

코드

#include <stdio.h>
#include <queue>
#include <string.h>

using namespace std;
int arr[100][100];
int visit[100][100];
int num;
int Min=99999;
int Max =0;

int _x[4] = {0,0,1,-1};
int _y[4] = {1,-1,0,0};

int check(int mid){ // mid는 최솟값과 최대값의 차이  
	
	
	for(int i=Min;i<=Max;i++){ // min부터 Max 사이의 mid 만큼의 간격 i ~ i+mid 
		if(arr[0][0]<i || arr[0][0]>mid+i){
			continue;
		}
		queue<pair<int,int> > q;
		memset(visit, 0, sizeof(visit));
		q.push(make_pair(0,0));
		visit[0][0]=1;
		while(!q.empty()){
			if(q.front().first == num-1 && q.front().second == num-1){
				return 1;
			}
			for(int j=0;j<4;j++){
				int xx = q.front().first + _x[j];
				int yy = q.front().second +_y[j];
				
				if(xx>=0&&xx<num&&yy>=0&&yy<num&&visit[xx][yy]==0){
					if(arr[xx][yy]>=i && arr[xx][yy]<=mid+i){
						q.push(make_pair(xx,yy));
						visit[xx][yy]=1;
					}
					
				}
			}
			q.pop();
		}
	}
	return 0;
}

int main(){
	
	scanf("%d",&num);
	for(int i=0;i<num;i++){
		for(int j=0;j<num;j++){
			scanf("%d",&arr[i][j]);
			
			if(arr[i][j]>Max){
				Max = arr[i][j];
			}
			if(arr[i][j]<Min){
				Min = arr[i][j];
			}
		}
			
	}
	
	int start = 0;
	int end = Max;
	while(start<=end){
		int mid = (start+end)/2;
		
		if(check(mid)){ // 성공 
			end = mid-1;
		}else{ // 실패 
			start = mid +1;
		}
	}
	printf("%d",start);
}