[BOJ] 1926 - 그림(Java)

📔문제 설명

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

안녕하세요! 오늘은 대표적인 그래프 탐색 문제인 백준 1926번 '그림' 문제 풀이 과정을 공유하려고 합니다.

단순히 정답 코드를 나열하기보다, 제가 처음에 어떤 실수를 했고 그 과정에서 무엇을 배워 코드를 개선했는지를 담아보았습니다.

이 문제는 주어진 도화지(2차원 배열)에서 연결된 그림의 총 개수와, 그중 가장 넓은 그림의 넓이를 출력하는 문제입니다.

---

🔍 접근법

첫 번째 접근: "모든 넓이를 저장하고 나중에 정렬하자"

처음에는 이렇게 생각했습니다.

"DFS로 그림을 하나씩 찾을 때마다 그 넓이를 계산해서, ArrayList에 모든 그림의 넓이를 저장하자. 탐색이 다 끝나면 리스트를 내림차순으로 정렬해서 첫 번째 값을 가져오면 그게 최댓값이겠지!"

이 아이디어는 논리적으로는 그럴듯해 보였습니다. 하지만 이 접근법은 치명적인 예외 케이스를 고려하지 못했습니다.

 

문제 발생: 50%에서 IndexOutOfBoundsException

제출하니 계속 50% 근처에서 틀렸습니다. 원인은 "그림이 하나도 없는 경우" 였습니다.

그림이 하나도 없다면 if(!visited[i][j] && graph[i][j] == 1) 조건을 만족하는 경우가 없어 DFS가 한 번도 실행되지 않습니다. 결국 넓이를 저장하기로 했던 ArrayList는 텅 비어있게 되죠.

그런데 제 코드는 마지막에 list.get(0)으로 가장 큰 값을 가져오려고 시도했습니다. 비어있는 리스트에 get(0)을 호출하니 당연히 IndexOutOfBoundsException이 발생한 것입니다.

 

해결 및 최적화: "굳이 리스트가 필요할까?"

오류의 원인을 찾던 중 문득 이런 생각이 들었습니다.

"나는 모든 그림의 넓이가 필요한 게 아니라, '가장 넓은' 그림의 넓이만 필요한데, 굳이 모든 값을 리스트에 저장해야 할까?"

그렇습니다. 필요한 것은 최댓값 하나뿐이었습니다. ArrayList를 선언하고, 모든 값을 저장하고, 정렬하는 과정은 모두 불필요한 낭비였습니다.

그래서 접근법을 다음과 같이 수정했습니다.

1. 가장 넓은 그림의 넓이를 저장할 maxPictureSize 변수를 0으로 초기화한다.
2. dfs 함수는 탐색을 마친 후, 해당 그림의 넓이를 반환하도록 설계한다.
3. DFS가 끝날 때마다 반환된 넓이와 maxPictureSize를 Math.max()로 비교하여 더 큰 값으로 갱신한다.

이 방식은 아래와 같은 장점이 있었습니다.

• 메모리 효율: ArrayList를 사용하지 않아 메모리 사용량이 줄어듭니다.
• 시간 효율: O(N log N)의 정렬 과정이 사라져 더 빠릅니다.
• 예외 처리: 그림이 하나도 없어도 maxPictureSize는 초기값인 0을 그대로 유지하므로, IndexOutOfBoundsException 같은 오류 없이 자연스럽게 "최대 넓이 0"이라는 결과를 얻을 수 있습니다.

---

💻 코드

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

public class Main {
    static int n,m;
    static int pictureCnt= 0; // 그림 갯수
    static int maxPictureSize=0; // 그림 최대 넓이
    static int[] dx = {0, 0, -1, 1}; // 상하좌우
    static int[] dy = {-1, 1, 0, 0};
    static int[][] graph;
    static boolean[][] visited;

    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());

        graph = new int[n][m];
        visited = new boolean[n][m];

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(!visited[i][j] && graph[i][j] == 1){
                    pictureCnt++;
                    maxPictureSize = Math.max(dfs(i, j), maxPictureSize);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(pictureCnt).append("\\n").append(maxPictureSize);

        System.out.println(sb);
    }

    static int dfs(int x, int y){
        visited[x][y] = true;
        int size = 1;

        for(int i=0; i<=3; i++){
            int newX = x+dx[i];
            int newY = y+dy[i];

            if(checkRange(newX, newY) && !visited[newX][newY] && graph[newX][newY] == 1){
                size += dfs(newX, newY);
            }
        }

        return size;
    }

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

---

💡 마무리

이번 문제를 통해 "요구사항을 정확히 파악하고 그에 맞는 최소한의 자원을 사용하는 것"의 중요성을 다시 한번 깨달았습니다. 단순히 기능을 구현하는 것을 넘어, 발생할 수 있는 예외 케이스를 고민하고 더 효율적인 방법을 찾는 과정이야말로 알고리즘의 묘미인 것 같습니다.

또한, ArrayList의 get(0) 호출 시 비어있는 리스트에 대한 예외 처리가 얼마나 중요한지, 그리고 만약 정말로 리스트 정렬이 필요했다면 Collections.sort(list, Collections.reverseOrder())를 사용해야 한다는 점도 다시 한번 상기하는 계기가 되었습니다.

---