어흥
[백준 22116] 창영이와 퇴근 (Java) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/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);
}
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 12904] A와 B (C++) (0) | 2021.08.07 |
---|---|
[백준 17265] 나의 인생에는 수학과 함께 (Java) (6) | 2021.07.27 |
[백준 1662] 압축 (Java) (0) | 2021.06.21 |
[백준 17616] 등수 찾기 (Java) (0) | 2021.06.17 |
[백준 2637] 장난감조립 (Java) (0) | 2021.06.17 |
Comments