boj 1981: 배열에서 이동

배열의 (1, 1)~(n, n)까지 이동할 때, 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 문제이다.

배열에서 이동하는 모든 경우를 완전탐색 할 경우 O(4^N)이 걸릴 것이다.

 

이런 경우 최댓값과 최솟값을 차이를 무작정 구하는 방법 보다는,

최댓값과 최솟값을 차이를 정해두고 가능한지 여부를 보는 방법이 더 쉬울 수 있다.

 

 

1차 시도 - 이분탐색을 사용하자

 

처음 생각한 문제 풀이 과정은 아래와 같다.

1. 이진 탐색으로 최대-최소 차이를 정한다.

2. (1, 1) -> (n, n)로 차이 내에 갈 수 있는지 bfs로 탐색한다.

 

이 경우에는 차이를 구하더라도 이에 맞는 쌍을 구해야 하는데,

이때 해당하는 쌍을 구할 때 이중for문을 사용하기보다는 두 포인터를 이용하여 시간을 줄이도록 했다.

import java.util.*;

public class Main {
	public static int dr[] = { 0, 0, 1, -1 };
	public static int dc[] = { 1, -1, 0, 0 };

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int mat[][] = new int[n][n];
		TreeSet<Integer> set = new TreeSet<Integer>();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				mat[i][j] = in.nextInt();
				set.add(mat[i][j]);
			}
		}

		int[] numbers = set.stream().mapToInt(i -> i).toArray();
		System.out.println(findDifference(numbers, mat, n));
	}

	private static int findDifference(int[] numbers, int[][] mat, int n) { // 이분탐색
		int length = numbers.length;
		int start = 0;
		int end = numbers[length - 1] - numbers[0];
		int answer = Integer.MAX_VALUE;

		while (start <= end) {
			int mid = (start + end) / 2;
			if (findMaxMinFromDifference(mat, numbers, mid, n)) {
				answer = mid; // 경로가 존재하니까 일단 저장
				end = mid - 1; // 더 줄여보자
			} else {
				start = mid + 1;
			}
		}

		return answer;
	}

	private static boolean findMaxMinFromDifference(int mat[][], int[] numbers, int diff, int n) { // 투 포인터
		int length = numbers.length;

		int start = 0;
		int end = 0;

		while (start < length && end < length) {
			if (numbers[end] - numbers[start] > diff) {
				start++;
			} else {

				if (bfs(mat, numbers[end], numbers[start], n)) {
					return true;
				}
				end++;
			}
		}

		return false;
	}

	// 최댓값과 최솟값의 차이가 min 보다 클 경우 false 리턴
	public static boolean bfs(int[][] mat, int max, int min, int n) { // bfs

		if (!isValuePossible(mat[0][0], max, min)) {
			return false;
		}

		Queue<Route> queue = new LinkedList<Route>();
		queue.add(new Route(0, 0));
		boolean[][] isVisited = new boolean[n][n];
		isVisited[0][0] = true;

		while (!queue.isEmpty()) {
			Route route = queue.poll();

			if (route.row == n - 1 && route.col == n - 1) {
				return true;
			}

			for (int i = 0; i < 4; i++) {
				int newRow = route.row + dr[i];
				int newCol = route.col + dc[i];

				if (isBoundary(newRow, newCol, n) && !isVisited[newRow][newCol]
						&& isValuePossible(mat[newRow][newCol], max, min)) {
					Route newRoute = new Route(newRow, newCol);
					isVisited[newRow][newCol] = true;

					queue.add(newRoute);
				}
			}
		}
		return false;
	}

	public static boolean isValuePossible(int value, int max, int min) {
		if (value < min) {
			return false;
		}
		if (value > max) {
			return false;
		}
		return true;
	}

	public static boolean isBoundary(int row, int col, int n) {
		if (row < 0) {
			return false;
		}
		if (row >= n) {
			return false;
		}
		if (col < 0) {
			return false;
		}
		if (col >= n) {
			return false;
		}
		return true;
	}
}

class Route {
	int row;
	int col;

	public Route(int row, int col) {
		this.row = row;
		this.col = col;
	}
}

 

생각해보니 굳이 이분탐색으로 범위를 줄여서 또 두 포인터로 각각 최대/최소 원소를 구하는 것은 연산이 중복되는 느낌이 들었다..ㅋㅋㅋ

따라서 이분탐색 부분은 제외하고 두 포인터와 bfs를 이용한 풀이로 다시 고쳐보았다.

추가적으로 isVisited의 경우 함수 내에서 계속 새로 할당할 경우 시간이 더 걸릴 수 있으므로 재사용하는 부분을 추가했다.

import java.util.*;

public class Main {
	public static int dr[] = { 0, 0, 1, -1 };
	public static int dc[] = { 1, -1, 0, 0 };
	public static boolean isVisited[][];

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int mat[][] = new int[n][n];
		isVisited = new boolean[n][n];

		TreeSet<Integer> set = new TreeSet<Integer>();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				mat[i][j] = in.nextInt();
				set.add(mat[i][j]);
			}
		}

		int[] numbers = set.stream().mapToInt(i -> i).toArray();
		System.out.println(findMaxMin(mat, numbers, n));
	}

	private static int findMaxMin(int mat[][], int[] numbers, int n) { // 투 포인터로 max, min 정하기
		int length = numbers.length;

		int start = 0;
		int end = 0;

		int answer = Integer.MAX_VALUE;

		while (start < length && end < length) {
			int diff = numbers[end] - numbers[start];
			if (bfs(mat, numbers[end], numbers[start], n)) {
				answer = Math.min(answer, diff); // 가능한 경로이므로 일단 저장

				start++; // 더 줄여보자
			} else {
				end++; // 불가능한 경로이므로 diff 범위를 늘리자
			}
		}

		return answer;
	}

	public static boolean bfs(int[][] mat, int max, int min, int n) { // bfs 가능한 경로 탐색
		if (!isPossible(0, 0, n, max, min, mat)) {
			return false;
		}

		clearMatrix(isVisited, n);

		Queue<Route> queue = new LinkedList<Route>();
		queue.add(new Route(0, 0));
		isVisited[0][0] = true;

		while (!queue.isEmpty()) {
			Route route = queue.poll();

			if (route.row == n - 1 && route.col == n - 1) {
				return true;
			}

			for (int i = 0; i < 4; i++) {
				int newRow = route.row + dr[i];
				int newCol = route.col + dc[i];

				if (isPossible(newRow, newCol, n, max, min, mat) && !isVisited[newRow][newCol]) {
					Route newRoute = new Route(newRow, newCol);
					isVisited[newRow][newCol] = true;

					queue.add(newRoute);
				}
			}
		}
		return false;
	}

	public static void clearMatrix(boolean[][] isVisited, int n) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				isVisited[i][j] = false;
			}
		}
	}

	public static boolean isPossible(int row, int col, int n, int max, int min, int[][] mat) {
		// 바운더리 안에 존재하며, [min, max]인 값임을 확인
		if (row < 0) {
			return false;
		}
		if (row >= n) {
			return false;
		}
		if (col < 0) {
			return false;
		}
		if (col >= n) {
			return false;
		}
		if (mat[row][col] < min) {
			return false;
		}
		if (mat[row][col] > max) {
			return false;
		}

		return true;
	}
}

class Route {
	int row;
	int col;

	public Route(int row, int col) {
		this.row = row;
		this.col = col;
	}

	@Override
	public String toString() {
		return "(" + row + ", " + col + ")";
	}
}