[JAVA] BOJ 백준 1981번 - 배열에서 이동

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

https://www.acmicpc.net/problem/1981

1981번: 배열에서 이동

---

2. 내가 푼 방법

무작정 (n, n) 위치까지 이동하기보다, (최대 - 최소) 값이 나올 수 있는 경우를 나열한 뒤에 필요한 탐색이 이뤄져야 한다.

 

투포인터를 사용하기 위해 배열의 모든 숫자가 담긴 list를 정렬한다. s는 0부터, e는 (1, 1) 혹은 (n, n)의 최대 값의 인덱스부터 시작한다. 또한, s의 범위는 (1, 1) 혹은 (n, n)의 최솟값을 넘어가면 도달할 수 없기 때문에, while문 조건에 s <= list.indexOf(min) 을 추가해주면 시간이 단축될 것이다.

 

minStandard부터 maxStandard 사이의 값을 가질 수 있는 상황이 만들어졌다. 이제 BFS 알고리즘을 통해 (1, 1)에서 (n , n)까지 이동이 가능한지 확인하고, 가능하다면 s 인덱스를, 그렇지 않다면 e 인덱스를 움직이면서 값이 나올 수 있는 범위를 조절하면서 최솟값을 찾으면 된다.

public static void solution() {
    int min = Math.min(arr[0][0], arr[N-1][N-1]);
    int max = Math.max(arr[0][0], arr[N-1][N-1]);

    Collections.sort(list);

    int s = 0;
    int e = list.indexOf(max);

    while (s <= e && s <= list.indexOf(min) && e < list.size()) {
        int minStandard = list.get(s);
        int maxStandard = list.get(e);
        int diff = maxStandard - minStandard;

        if (bfs(minStandard, maxStandard)) {
            result = Math.min(result, diff);
            s++;
        }
        else e++;
    }
}

public static boolean bfs(int min, int max) {
    Queue<int[]> queue = new ArrayDeque<>();
    boolean[][] visit = new boolean[N][N];

    visit[0][0] = true;
    queue.add(new int[]{0, 0});

    while (!queue.isEmpty()) {
        int[] q = queue.poll();

        for (int d = 0; d < dx.length; d++) {
            int nx = q[0] + dx[d];
            int ny = q[1] + dy[d];

            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if (visit[nx][ny] || arr[nx][ny] < min || max < arr[nx][ny]) continue;

            if (nx == N-1 && ny == N-1) {
                return true;
            }

            visit[nx][ny] = true;
            queue.add(new int[]{nx, ny});
        }
    }

    return false;
}

 

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B1981.java

import java.util.*;
import java.io.*;

class Main {
    static int N;
    static int[][] arr;
    static List<Integer> list;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int result;

    public static void main (String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        int min = Math.min(arr[0][0], arr[N-1][N-1]);
        int max = Math.max(arr[0][0], arr[N-1][N-1]);

        Collections.sort(list);

        int s = 0;
        int e = list.indexOf(max);

        while (s <= e && s <= list.indexOf(min) && e < list.size()) {
            int minStandard = list.get(s);
            int maxStandard = list.get(e);
            int diff = maxStandard - minStandard;

            if (bfs(minStandard, maxStandard)) {
                result = Math.min(result, diff);
                s++;
            }
            else e++;
        }
    }

    public static boolean bfs(int min, int max) {
        Queue<int[]> queue = new ArrayDeque<>();
        boolean[][] visit = new boolean[N][N];

        visit[0][0] = true;
        queue.add(new int[]{0, 0});

        while (!queue.isEmpty()) {
            int[] q = queue.poll();

            for (int d = 0; d < dx.length; d++) {
                int nx = q[0] + dx[d];
                int ny = q[1] + dy[d];

                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if (visit[nx][ny] || arr[nx][ny] < min || max < arr[nx][ny]) continue;

                if (nx == N-1 && ny == N-1) {
                    return true;
                }

                visit[nx][ny] = true;
                queue.add(new int[]{nx, ny});
            }
        }

        return false;
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        list = new ArrayList<>();
        result = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());

                if (!list.contains(arr[i][j])) {
                    list.add(arr[i][j]);
                }
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

얼마 전에 푼 https://www.acmicpc.net/problem/2842 문제와 비슷해서 금방 풀 수 있었다. 무작정 탐색하기보다 경우의 수를 줄일 수 있는 방법이 존재하는지 고민하는 연습을 해야겠다.