[ 백준 1981 ] 배열에서 이동

1. 문제

1981번: 배열에서 이동

 

2. 풀이

우선 (1, 1) 에서 (N, N)으로 가는 모든 경로를 탐색해야 하는 BFS 문제임은 맞지만, (최대 - 최소) 값이 최소가 되게 만들기 위해서 경로를 탐색하기 위해서는 특정한 기준이 필요하다. 여기서 기준이란 모든 경우를 만들어서 값을 만들어 볼 수는 없으니, 기준값을 만들어 해당 값으로 배열에서 (1, 1)부터 (N, N)까지의 경로가 있는지 확인하는 것이다. 그렇다면 이 기준을 어떻게 만들어 줄 것 인가에 초점을 맞춰야 한다.

 

이분탐색을 통한 기준점 마련

먼저 배열을 입력받을 때 우리는 최솟값과 최댓값을 미리 판단할 수가 있다. 이 두 값을 통해서 입력 받은 배열에서 (최대 - 최소)의 최댓값을 미리 산정할 수 있게 된다. 이를 통해 배열에서 만드는 경로는 '0 ~ (최댓값 - 최솟값)'의 범위의 응답값을 만들어 낼 수 있다는 것을 알 수 있다. 이 범위 내에서 이분탐색을 통해 mid 값을 만들고, BFS를 통해 mid 이하의 최종 응답값을 만들어내는 경로가 있는지 탐색한다. 이하 설명에서는 mid를 차이값으로 명명한다.

 

풀이 정리

1. 배열 입력 시, 배열 요소의 최솟값과 최댓값 판단
   1. 초기 최댓값 = 배열 요소 최댓값 - 배열 요소 최솟값
2. (0 ~ 초기 최댓값) 범위 내에서 이분탐색 실행
   1. 이분탐색의 기본 개념을 이용한 차이값 산출
   2. mid = (left + right) / 2 
3. 이분탐색으로 만들어낸 mid(차이값)으로 탐색이 가능한지 BFS를 통해 확인
   1. 배열 최솟값 부터 최솟값에 차이값을 더한 범위 내에서 (N, N)까지 이동할 수 있는가를 확인

 

3. 소스코드

public class Main {
    static final int[] dy = {-1, 0, 1, 0};
    static final int[] dx = {0, 1, 0, -1};

    static int N, min = 201, max = -1;
    static int ans;
    static int[][] map;

    static void binary(int left, int right) {
        while (left <= right) {
            int mid = (left + right) / 2;

            if (bfs(mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
    }

    static boolean bfs(int diff) {
        for (int flag = min; flag + diff <= max; flag++) {
            int start = flag;
            int end = flag + diff;

            if (map[0][0] < start || end < map[0][0]) continue;

            boolean[][] visit = new boolean[N][N];

            Queue<Integer> q = new LinkedList<>();
            q.add(0);
            visit[0][0] = true;

            while (!q.isEmpty()) {
                Integer now = q.poll();
                if (now / N == N - 1 && now % N == N - 1) {
                    return true;
                }

                for (int dir = 0; dir < 4; dir++) {
                    int ny = now / N + dy[dir];
                    int nx = now % N + dx[dir];

                    if (ny < 0 || nx < 0 || N <= ny || N <= nx || visit[ny][nx] || map[ny][nx] < start || end < map[ny][nx]) continue;

                    q.add(ny * N + nx);
                    visit[ny][nx] = true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());

        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                min = Math.min(min, map[i][j]);
                max = Math.max(max, map[i][j]);
            }
        }

        binary(0, max - min);

        bw.write(ans + "");
        bw.close();
        br.close();
    }
}

 

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code

---

BFS 개념은 아래 게시글 참고♥️

그래프와 BFS(Graph & Breadth First Search)