백준 1981 : 배열에서 이동

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

1981번: 배열에서 이동

 

 

접근방법

---

이 문제에서는 이분탐색 + BFS를 이용하였습니다.

 

제 풀이는 다음과 같은 3단계로 구성되었습니다.

최댓값과 최솟값의 차이를 이분탐색을 이용하여 구합니다.

해당 차이를 가진 모든 경우의 수를 구합니다.

각 경우의 수마다 BFS를 통해 (1, 1)에서 (n, n)까지 이동할 수 있는지 체크합니다.

 

 

순서

---

1.  배열의 수를 검사하여 전체 최댓값과 최솟값을 구합니다.
2.  0 ~ (최댓값 - 최솟값)의 범위를 기준으로 이분탐색합니다.  (최댓값 - 최솟값)을 사용하는 이유는 현재 경우에서 나올 수 있는 차이의 최댓값이기 때문입니다.
   1.  설정한 차이를 기준으로 배열에서 이동할 때 거쳐갈 수 있는 숫자의 최댓값과 최솟값을 설정합니다. 예를 들어 차이가 8일 때 배열을 전부 이동할 수 있는지 알기 위해 (최댓값 : 8, 최솟값 : 0), (최댓값 : 9, 최솟값 : 1), (최댓값 : 10, 최솟값 : 2), ... , (최댓값 : 200, 최솟값 : 192) 같은 모든 경우의 수를 검사합니다
      1.  현재 설정한 최댓값과 최솟값 사이의 수로만 (1, 1), (n, n)까지 이동할 수 있는지 BFS로 검사합니다. 
   2.  이동가능한 경우가 하나라도 있을 때 해당 차이도 가능하다는 것을 알 수 있습니다.
3.  설정한 차이가 가능한 경우 0 ~ (차이)를 기준으로 다시 이분탐색을 적용하고 설정한 차이가 불가능한 경우 더 큰 차이를 찾아야 하므로 (차이) ~ (최댓값 - 최솟값)을 기준으로 이분탐색을 적용합니다.

 

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, ans, MAX, MIN;
	static int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
	static int[][] arr;
	static Queue<Pos> que;
	static boolean[][] visited;
	
	static class Pos{
		int r, c;

		public Pos(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		
		MAX = 0;
		MIN = 200;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int tmp = Integer.parseInt(st.nextToken());
				
				arr[i][j] = tmp;
				if(tmp > MAX)  MAX = tmp;
				else if(tmp < MIN) MIN = tmp;
			}
		}
		
		binarySearch(0, MAX - MIN);
		
		System.out.print(ans);
	}

	private static void binarySearch(int s, int e) {
		if(s >= e) {
			ans = s;
			return;
		}
		int mid = (s + e) / 2;
		
		if(findMinMax(mid)) binarySearch(s, mid);
		else binarySearch(mid + 1, e);
	}
	
	private static boolean findMinMax(int mid) {
		for (int i = 0; i + mid <= 200; i++) {
			if(movePossible(i, i + mid)) return true;
		}
//		for (int i = MIN; i + mid <= MAX; i++) {
//			if(movePossible(i, i + mid)) return true;
//		}
		
		return false;
	}

	private static boolean movePossible(int min, int max) {
		que = new LinkedList<Pos>();
		visited = new boolean[N][N];
		
		if(min > arr[0][0] || max < arr[0][0]) return false;
		que.offer(new Pos(0, 0));
		visited[0][0] = true;
		
		while(!que.isEmpty()) {
			Pos pos = que.poll();
			
			if(pos.r == N - 1 && pos.c == N - 1) {
				return true;
			}
			
			for (int i = 0; i < 4; i++) {
				int nr = pos.r + dr[i];
				int nc = pos.c + dc[i];
				
				if(isOutOfMap(nr, nc)) continue;
				if(visited[nr][nc]) continue;
				if(min > arr[nr][nc] || max < arr[nr][nc]) continue;
				
				visited[nr][nc] = true;
				que.offer(new Pos(nr, nc));
			}
		}
		
		return false;
	}

	private static boolean isOutOfMap(int r, int c) {
		if(r < 0 || r >= N || c < 0 || c >= N) return true;
		return false;
	}
}

 

 

Reference

---

https://kyu9341.github.io/algorithm/2020/03/13/algorithm1981/