[백준] 1981번 - 배열에서 이동 (java)

[백준] 1981번 - 배열에서 이동 (java)

문제

n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 거쳐서 이동하게 된다. 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오.

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 5820 1455 947 23.616%

입력

첫째 줄에 n(2 ≤ n ≤ 100)이 주어진다. 다음 n개의 줄에는 배열이 주어진다. 배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이다.

출력

첫째 줄에 (최대 - 최소)가 가장 작아질 때의 그 값을 출력한다.

풀이

주어진 배열의 최솟값(min)과 최댓값(max)을 찾는다. 이분탐색을 사용하게 되는데 정답이 min과 max의 중간값(mid)라고 가정하고 bfs를 수행 해 본다. 2-1. 이 때 어떤 값의 차이만 알 뿐 시작값과 끝 값은 알 수 없으니 for문을 돌려서 될때까지 bfs를 해본다. 성공적으로 탐색했다면 차이를 더 줄여본다. 실패했다면 차이를 늘려본다. 성공할때마다 answer = Math.min(answer, mid)로 업데이트 한다. 이분탐색이 끝나면 결과를 출력한다.

최종 소스코드

package BJ_Practice; import java.io.*; import java.util.*; public class BJ_G1_1981_배열에서_이동 { static int N; static int[][] map; static boolean visited[][]; static int[][] deltas = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; static int min = 1000, max = 0; static StringTokenizer st; static class RC { int r, c; public RC(int r, int c) { super(); this.r = r; this.c = c; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); N = Integer.parseInt(br.readLine()); map = new int[N][N]; visited = new boolean[N][N]; for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < N; j++) { map[i][j] = Integer.parseInt(st.nextToken()); max = Math.max(max, map[i][j]); min = Math.min(min, map[i][j]); } } int start = 0; int end = max - min; int answer = 987654321; while (start <= end) { int mid = (start + end) / 2; boolean flag = false; for (int i = min; i <= max; i++) { // 차이가 mid인 값을 싹 다 탐색 if (i <= map[0][0] && map[0][0] <= i + mid) if (flag = bfs(i, i + mid)) // 경로가 하나라도 있으면 true -> break break; } if (flag) { end = mid - 1; answer = Math.min(answer, mid); // 경로가 있으면 차이를 정답에 반영 } else start = mid + 1; } System.out.println(answer); } static boolean bfs(int min, int max) { Queue queue = new LinkedList<>(); queue.offer(new RC(0, 0)); for (int i = 0; i < N ; i++) { Arrays.fill(visited[i], false); } visited[0][0] = true; while (!queue.isEmpty()) { RC curr = queue.poll(); if (curr.r == N - 1 && curr.c == N - 1) { // 목적지에 도달할 수 있으면 끝 return true; } for (int i = 0; i < 4; i++) { int nr = curr.r + deltas[i][0]; int nc = curr.c + deltas[i][1]; if (isIn(nr, nc) && !visited[nr][nc] && min <= map[nr][nc] && map[nr][nc] <= max) { //사이에 값 존재 queue.offer(new RC(nr, nc)); visited[nr][nc] = true; } } } return false; } static boolean isIn(int r, int c) { return r >= 0 && r < N && c >= 0 && c < N; } }

from http://skdltm117.tistory.com/47 by ccl(A) rewrite - 2021-12-17 03:28:18