문제
이해
NxN 배열에서 (1,1) -> (N,N) 까지 이동하려고 합니다. 이동은 상,하,좌,우로만 할 수 있습니다. 이동하기 위해 거쳐 간 수 중에서 최댓값, 최솟값의 차이가 가장 작아지는 경우의 값을 출력하면 됩니다.
접근
본 문제 같은 경우 웬만하면 그리디가 아닌 탐색쪽으로 접근하려고 합니다.
처음 접근했을 때의 아이디어는 이렇습니다. 우선, 출발지와 목적지가 확실하고 격자형이며 상하좌우로 이동하기 때문에 BFS를 기본 아이디어로 떠올렸습니다.
하지만 일반 BFS와 다르게 본 문제는 중복 방문을 허용합니다. 그렇기에 방문 조건을 다르게 설정할 필요가 있습니다.
방문 과정과 상관없이 현재의 최댓값, 최솟값은 고정되어 있습니다. 최댓값과 최솟값을 기준으로 방문처리를 할 수 있지 않을까 생각했습니다.
결론적으로 불가능했습니다. 가능한 범위는 1~200 이고 좌표까지 포함해야 하기 때문에 visted 배열은 200 x 200 x 100 x 100의 공간이 필요했습니다.
저는 입출력 예제를 보고 힌트를 얻었습니다. 만일 출발지가 1, 도착지가 5라면 정답의 최솟값은 4입니다. 또한, 우리가 BFS를 돌 때 노드가 1 ~ 5 사이가 아닌 곳은 방문할 수 없습니다.
그렇다면 반대로 접근하여 가능한 범위 중에서 최솟값을 탐색하는 아이디어를 떠올렸습니다.
기준을 범위 크기를 의미하는 최댓값 - 최솟값으로 잡고 가능한 범위 크기를 탐색해봅시다. 저는 이분탐색을 사용해 풀이했습니다.
범위 크기는 0~200 사이이기 때문에 최초에 mid 값을 100이라고 합시다. 범위 크기는 100이기 때문에 탐색해야 하는 범위는 (i, i+100) (단, i는 min과 max 사이) 가 됩니다.
따라서, 가능한 범위 중에서 BFS를 수행하고 만일 도착지까지 가능하다면 범위크기를 줄이고 불가능하다면 범위크기를 늘려서 이분탐색을 수행합니다.
풀이
private static int BinarySearch() {
int start = 0;
int end = max - min;
int ret = 1_000_000_000;
while (start <= end) {
int mid = (start + end) / 2;
boolean flag = false;
for (int i = min; i <= max; i++) {
if (i <= board[0][0] && board[0][0] <= i + mid) {
if (bfs(i, i + mid)) {
flag = true;
break;
}
}
}
if (flag) {
end = mid - 1;
ret = Math.min(ret, mid);
} else {
start = mid + 1;
}
}
return ret;
}위 코드는 범위 크기를 탐색하는 이분탐색 코드입니다. mid값을 기준으로 min, max에 따른 범위를 설정하고 각각 BFS를 수행합니다. BFS가 성공하면 가능하기 때문에 범위 크기를 더 줄이고 불가능하다면 크기를 늘립니다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static final int[][] d = { { -1, 0, 1, 0 }, { 0, 1, 0, -1 } };
static class xy {
int x;
int y;
public xy(int x, int y) {
this.x = x;
this.y = y;
}
}
static int N;
static int[][] board;
static int[] arr;
static StringTokenizer st = null;
static int min = 200, max = 0;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
board = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
min = Math.min(min, board[i][j]);
max = Math.max(max, board[i][j]);
}
}
System.out.println(BinarySearch());
}
private static int BinarySearch() {
int start = 0;
int end = max - min;
int ret = 1_000_000_000;
while (start <= end) {
int mid = (start + end) / 2;
boolean flag = false;
for (int i = min; i <= max; i++) {
if (i <= board[0][0] && board[0][0] <= i + mid) {
if (bfs(i, i + mid)) {
flag = true;
break;
}
}
}
if (flag) {
end = mid - 1;
ret = Math.min(ret, mid);
} else {
start = mid + 1;
}
}
return ret;
}
private static boolean bfs(int lower, int upper) {
boolean[][] visited = new boolean[N][N];
Queue<xy> q = new ArrayDeque<>();
q.add(new xy(0, 0));
visited[0][0] = true;
while (!q.isEmpty()) {
xy cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.x + d[0][i];
int ny = cur.y + d[1][i];
if (IsOutBound(nx, ny) || visited[nx][ny]) {
continue;
}
if (board[nx][ny] < lower || board[nx][ny] > upper) {
continue;
}
if (nx == N - 1 && ny == N - 1) {
return true;
}
q.add(new xy(nx, ny));
visited[nx][ny] = true;
}
}
return false;
}
private static boolean IsOutBound(int nx, int ny) {
return nx < 0 || nx >= N || ny < 0 || ny >= N;
}
}결과
리뷰
많은 시행착오가 있었던 문제였습니다. 메모리 생각을 미처 못했는데 코드를 작성하기 전에 검증을 확실히 하고 접근해야 할 것 같습니다.
