BOJ_1981_배열에서 이동 (Java, C++)

[Platinum V] 배열에서 이동 - 1981

문제 링크

성능 요약

메모리: 157272 KB, 시간: 364 ms

분류

너비 우선 탐색, 이분 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 12월 7일 05:28:49

문제 설명

n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다.

이와 같이 이동하다 보면, 배열에서 몇 개의 수를 거쳐서 이동하게 된다. 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오.

입력

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

출력

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

문제 풀이

• 총 시간복잡도: O((maxVal-minVal) * N² * log(maxVal-minVal))
• 총 공간복잡도: O(N²)

이분 탐색 + BFS 조합 사용

• 이분 탐색: 가능한 “최대값-최소값의 차이”를 찾기 위해
• BFS: 해당 차이로 경로가 가능한지 확인하기 위해

left 초기값: 시작점과 도착점의 차이 (이보다 작을 순 없음) right 초기값: 전체 배열의 최대값-최소값

놓쳤던 부분: if (!(board[1][1] >= i && board[1][1] <= j)) return false;

• 시작점이 범위 안에 있어야 한다는 조건을 놓치기 쉬움 이 조건이 없으면 시작부터 잘못된 경로 탐색 시작

실수하기 쉬운 부분 :

int j = i + mid;  // 올바른 방법
int j = minVal + mid;  // 틀린 방법

i~j 범위를 [i, i+mid]로 잡아야 하는데 실수로 몇번 틀림.

코드

Java코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int[] dr = {0, -1, 0, 1}, dc = {-1, 0, 1, 0};
	static int N, board[][], max=-210, min=210;
	static boolean visited[][];
	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
//		br = new BufferedReader(new InputStreamReader(System.in));
		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		board = new int[N+2][N+2];
		for(int i=0; i<N+2; i++) {
			Arrays.fill(board[i], -1);
		}
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				if(board[i][j] > max) max=board[i][j];
				if(board[i][j]<min) min = board[i][j];
			}
		}
		
		int res = 210;
		int left = Math.abs(board[1][1]-board[N][N]);
		int right = max-min;
		while(left<=right) {
			int mid = left + (right-left)/2;
			boolean flag = false;
			
			for(int i=min; i<=max-mid; i++) {
				int j = i + mid;
				if(board[1][1]>=i && board[1][1] <= j) {
					if(canGo(i, j)) {
						flag = true;
						break;
					}
				}
			}
			
			if(flag) {
				res = mid;
				right = mid-1;
			}
			else {
				left = mid+1;
			}
		}
		
		bw.write(String.valueOf(res));
		bw.flush();
		bw.close();
		br.close();
	}

	private boolean canGo(int min, int max) {
		Queue<int[]> queue = new LinkedList<int[]>();
		visited = new boolean[N+2][N+2];
		
		queue.offer(new int[]{1, 1});
		visited[1][1] = true;
		
		while(!queue.isEmpty()) {
			int[] curr = queue.poll();
			int currNum = board[curr[0]][curr[1]];
			
			if(curr[0] == N && curr[1] == N) return true;
			
			for(int k=0; k<4; k++) {
				int[] next = {curr[0] + dr[k], curr[1] + dc[k]};
				
				if(board[next[0]][next[1]] == -1 || visited[next[0]][next[1]]) continue;
				if(board[next[0]][next[1]] >= min && board[next[0]][next[1]] <= max) {
					queue.offer(next);
					visited[next[0]][next[1]] = true;
				}
			}
		}
		return false;
	}
}

---

C++코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int dr[] = {0, -1, 0, 1}, dc[] = {-1, 0, 1, 0};
int N;
vector<vector<int>> board;
vector<vector<bool>> visited;
int maxVal = -210, minVal = 210;

bool canGo(int i, int j) {
    if (!(board[1][1] >= i && board[1][1] <= j)) return false;

    queue<pair<int, int>> queue;
    visited.assign(N + 2, vector<bool>(N + 2, false));
    queue.push({1, 1});
    visited[1][1] = true;

    while (!queue.empty()) {
        int curr[] = {queue.front().first, queue.front().second};
        queue.pop();

        if (curr[0] == N && curr[1] == N) return true;

        for (int k = 0; k < 4; k++) {
            int next[] = {curr[0] + dr[k], curr[1] + dc[k]};
            if (board[next[0]][next[1]] == -1 || visited[next[0]][next[1]])
                continue;
            if (board[next[0]][next[1]] >= i && board[next[0]][next[1]] <= j) {
                queue.push({next[0], next[1]});
                visited[next[0]][next[1]] = true;
            }
        }
    }
    return false;
}

void solve() {
    cin >> N;

    board.assign(N + 2, vector<int>(N + 2, -1));
    visited.assign(N + 2, vector<bool>(N + 2, false));

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> board[i][j];
            maxVal = max(maxVal, board[i][j]);
            minVal = min(minVal, board[i][j]);
        }
    }

    int res = 210;
    int left = abs(board[1][1] - board[N][N]);
    int right = maxVal - minVal;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        bool flag = false;

        for (int i = minVal; i <= maxVal - mid; i++) {
            int j = i + mid;
            if (canGo(i, j)) {
                flag = true;
                break;
            }
        }

        if (flag) {
            right = mid - 1;
            res = mid;
        } else {
            left = mid + 1;
        }
    }
    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    // cin >> tt;    // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}