[백준 22116] 창영이와 퇴근 (Java)

문제 링크: https://www.acmicpc.net/problem/22116

22116번: 창영이와 퇴근

1. 주의할 점

- 여러가지 푸는 방식이 존재하지만, 1씩 증가시키면서 10억까지 테스트 → TLE 발생

 

2. 구현

- BFS+이분탐색을 통해 차이가 Mid이하라면 전진이 가능하다고 판단

- L=0, R=10억, Result = R-L로 초기화 하고 이분탐색을 시작한다

- Mid = L+(R-L)/2를 통해 Mid값을 갱신하고, BFS()가 가능하면 Result의 값도 갱신한다

 

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static final int dx[] = {0,1,0,-1};
    static final int dy[] = {-1,0,1,0};
    static int num,l,r,result,mid;
    static int arr[][];
    static boolean check[][];
    
    static class Info{
        int y,x;
        
        public Info(int y, int x){
            this.y=y;
            this.x=x;
        }
    }
    
    static boolean bfs(){
        //초기화
        check = new boolean[num][num];
        Queue<Info> q = new LinkedList<>();
        q.offer(new Info(0,0));
        check[0][0]=true;
        
        while(!q.isEmpty()){
            Info ii = q.poll();
            int cy = ii.y;
            int cx = ii.x;
            if(cy==num-1 &&cx==num-1) return true;
            for(int i=0;i<4;i++){
                int nx = cx+dx[i];
                int ny = cy+dy[i];
                if(nx>=0 && ny>=0 && nx<num && ny<num && !check[ny][nx]){
                    int val = Math.abs(arr[cy][cx]-arr[ny][nx]);
                    if(val<=mid){
                        check[ny][nx]=true;
                        q.offer(new Info(ny,nx));
                    }
                }
            }
        }
        return false;
    }
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    num = Integer.parseInt(br.readLine().trim());
	    //초기화
	    arr = new int[num][num];
	    l=0;
	    r=1000000000;
	    for(int i=0;i<num;i++){
	        String str = br.readLine();
	        StringTokenizer st = new StringTokenizer(str);
	        for(int j=0;j<num;j++)
	            arr[i][j] = Integer.parseInt(st.nextToken());
	    }
	    result = r-l;
	    
	    while(l<=r){
	        mid = l+(r-l)/2;
	        if(bfs()){
	            result = mid;
	            r = mid-1;
	        }
	        else
	            l = mid+1;
	    }
	    System.out.print(result);
	}
}