배열의 (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 + ")";
}
}
'알고리즘 공부 > boj' 카테고리의 다른 글
| boj 1005: ACM Craft (0) | 2021.01.20 |
|---|---|
| boj 1949: 우수 마을 (0) | 2021.01.19 |
| boj 3745: 오름세 (0) | 2021.01.15 |
| boj 1091: 카드 섞기 (0) | 2021.01.11 |
| boj 1153: 네 개의 소수 (0) | 2021.01.10 |
