[자바/DFS/런타임에러] 코드트리 IL : 안전지대

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

런타임 에러는 십중팔구 IndexOutOfBoundException 문제이다. 인덱스 에러가 발생할 수 있는 포인트를 확인하여 디버깅해야 한다.

package 코드트리.그래프.DFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class 안전_지대 {
    public static int n, m;
    public static int[] dx = new int[]{0, 1, 0, -1};
    public static int[] dy = new int[]{1, 0, -1, 0};
    public static int[][] visited;
    public static int[][] grid;
    public static Map<Integer, Integer> map = new HashMap<>();
    public static int threshold;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        threshold = Integer.MIN_VALUE;
        grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                int num = Integer.parseInt(st.nextToken());
                grid[i][j] = num;
                threshold = Math.max(threshold, num);
            }
        }
        for (int k = 1; k <= 100; k++) {
            if (k > threshold) {
                break;
            }
            visited = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (canGo(i, j, k)) {
                        map.put(k, map.getOrDefault(k, 0) + 1);
                        visited[i][j] = 1;
                        DFS(i, j, k);
                    }
                }
            }
        }
        ArrayList<Map.Entry<Integer, Integer>> entries = new ArrayList<>(map.entrySet());
        Collections.sort(entries, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                if (o1.getValue().equals(o2.getValue())) {
                    return o1.getKey().compareTo(o2.getKey());
                }
                return o2.getValue().compareTo(o1.getValue());
            }
        });
        System.out.println(entries.get(0).getKey() + " " + entries.get(0).getValue());

    }

    public static void DFS(int y, int x, int k) {
        for (int i = 0; i < 4; i++) {
            int newY = y + dy[i];
            int newX = x + dx[i];
            if (canGo(newY, newX, k)) {
                visited[newY][newX] = 1;
                DFS(newY, newX, k);
            }
        }
    }

    public static boolean canGo(int y, int x, int k) {
        if (!inRange(y, x) || grid[y][x] <= k || visited[y][x] == 1) {
            return false;
        }
        return true;
    }

    public static boolean inRange(int y, int x) {
        return y >= 0 && y < n && x >= 0 && x < m;
    }
}

기본적으로 DFS를 수행할 때, canGo와 inRange를 이용하여 index 에러가 발생하지 않도록 제어해 주었는데, index 에러가 발생하였다. 따라서 가장 먼저 의심해봐야 하는 곳은 entries라고 명명한 arrayList일 것이다. 정렬을 거친 뒤 get(0)를 통해 값을 출력하고자 했는데, index 에러가 난다는 것은, 아무런 값도 입력되지 않는다는 것이다. 따라서 초기화를 시켜주면 된다고 생각했다. 아무런 값도 입력되지 않는다는 것은 k가 1일 때부터 모든 경우에서 grid가 전부 물에 잠기는 경우이므로 1,0 으로 초기화해주었다.

 

package 코드트리.그래프.DFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class 안전_지대 {
    public static int n, m;
    public static int[] dx = new int[]{0, 1, 0, -1};
    public static int[] dy = new int[]{1, 0, -1, 0};
    public static int[][] visited;
    public static int[][] grid;
    public static Map<Integer, Integer> map = new HashMap<>();
    public static int threshold;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        threshold = Integer.MIN_VALUE;
        grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                int num = Integer.parseInt(st.nextToken());
                grid[i][j] = num;
                threshold = Math.max(threshold, num);
            }
        }
        map.put(1, 0); // edited
        for (int k = 1; k <= 100; k++) {
            if (k > threshold) {
                break;
            }
            visited = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (canGo(i, j, k)) {
                        map.put(k, map.getOrDefault(k, 0) + 1);
                        visited[i][j] = 1;
                        DFS(i, j, k);
                    }
                }
            }
        }
        ArrayList<Map.Entry<Integer, Integer>> entries = new ArrayList<>(map.entrySet());
        Collections.sort(entries, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                if (o1.getValue().equals(o2.getValue())) {
                    return o1.getKey().compareTo(o2.getKey());
                }
                return o2.getValue().compareTo(o1.getValue());
            }
        });
        System.out.println(entries.get(0).getKey() + " " + entries.get(0).getValue());

    }

    public static void DFS(int y, int x, int k) {
        for (int i = 0; i < 4; i++) {
            int newY = y + dy[i];
            int newX = x + dx[i];
            if (canGo(newY, newX, k)) {
                visited[newY][newX] = 1;
                DFS(newY, newX, k);
            }
        }
    }

    public static boolean canGo(int y, int x, int k) {
        if (!inRange(y, x) || grid[y][x] <= k || visited[y][x] == 1) {
            return false;
        }
        return true;
    }

    public static boolean inRange(int y, int x) {
        return y >= 0 && y < n && x >= 0 && x < m;
    }
}