17025 - Icy Perimeter (Java)

📌 문제 설명

백준 17025번 - 얼음 깨기 대회

• N x N 크기의 격자에서 #은 얼음 덩어리를, .은 빈 칸을 의미함.
• 여러 개의 얼음 덩어리가 존재할 수 있으며, 각 덩어리는 4방향(상하좌우)으로 연결된 #을 포함.
• 목표: 가장 큰 얼음 덩어리의 크기(answer1)와 그 덩어리의 둘레 길이(answer2)를 구하는 문제.
• 만약 같은 크기의 덩어리가 여러 개라면, 둘레 길이가 가장 작은 덩어리를 선택.

---

💡 접근 방식

🔹 1️⃣ BFS를 활용한 영역 탐색

1. BFS를 사용하여 #로 연결된 얼음 덩어리를 찾음.
2. 방문 여부를 저장하는 visited[][] 배열을 활용하여 중복 탐색 방지.
3. 각 덩어리에 대해
   • 크기(size)를 측정
   • 둘레(length)를 측정 (#이 아닌 곳과 맞닿은 부분)

🔹 2️⃣ BFS로 덩어리 크기 및 둘레 길이 계산

• Queue<int[]>를 사용하여 BFS 탐색.
• 둘레 길이 측정 방식
  • #이 아닌 칸(.) 또는 격자 밖의 영역과 접촉할 때마다 length++ 증가.

🔹 3️⃣ 가장 큰 덩어리 및 최소 둘레 길이 저장

• 최대 크기의 얼음 덩어리를 찾고, 같은 크기일 경우 둘레 길이가 작은 것을 선택.

---

✅ 정답 코드 (BFS)

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

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer st;
    private static int N;
    private static char[][] map;
    private static boolean[][] visited;
    private static int answer1, answer2;

    public static void main(String[] args) throws IOException {
        setting();
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == '#' && !visited[i][j]) {
                    visited[i][j] = true;
                    bfs(i, j);
                }
            }
        }
        System.out.println(answer1 + " " + answer2);
    }

    private static void bfs(int x, int y) {
        int size = 0, length = 0;
        int[] dix = {-1, 0, 1, 0};
        int[] diy = {0, 1, 0, -1};

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int cx = cur[0];
            int cy = cur[1];
            size++;

            for (int i = 0; i < 4; i++) {
                int dx = cx + dix[i];
                int dy = cy + diy[i];

                if (dx < 0 || dx >= N || dy < 0 || dy >= N || map[dx][dy] != '#') {
                    length++; // 격자 밖이거나 '.'이면 둘레 증가
                    continue;
                }

                if (!visited[dx][dy]) {
                    visited[dx][dy] = true;
                    queue.add(new int[]{dx, dy});
                }
            }
        }

        if (answer1 < size) { // 더 큰 얼음 덩어리 발견
            answer1 = size;
            answer2 = length;
        } else if (answer1 == size) { // 같은 크기면 최소 둘레 선택
            answer2 = Math.min(answer2, length);
        }
    }

    private static void setting() throws IOException {
        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String inputString = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = inputString.charAt(j);
            }
        }
    }
}

---

🔍 코드 분석

함수	역할
setting()	입력 처리 및 지도 저장
bfs(x, y)	BFS 탐색을 통해 얼음 덩어리 크기 및 둘레 길이 계산
visited[][]	방문한 얼음 덩어리 위치를 저장

---

🚀 최적화 및 개선점

✅ 1️⃣ Queue<int[]> 대신 Deque<int[]> 사용 (메모리 최적화)

• LinkedList 기반 Queue는 메모리 사용량이 높음 → ArrayDeque가 더 적합.
• Queue<int[]> queue = new LinkedList<>();
  → Deque<int[]> queue = new ArrayDeque<>(); 변경.

  자바 공식문서에 다음과 같이 설명이 되어 있어요.
  This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.
  ArrayDeque는 Array에 의해 지원되고 Array는 LinkList보다 cache locality-friendly 하다.
  메모리에서 데이터를 읽고 쓸 때 캐시의 효과를 최대한 누릴 수 있도록 설계되었다.
  많은 데이터가 삽입, 삭제가 빈번하게 발생할 때에도 ArrayDeque가 LinkedList보다 성능적으로도 메모리적으로도 효율적이다.

---

실제로 비교해보았을때,

밑에 부분이 ArrayDeque를 사용한 코드인데 속도가 크게 차이나지는 않는다. 하지만, 더 큰 범위와 데이터를 관리해야되는 상황에서는 발생할 수 있다고 생각한다. 캐시 기능을 제공해주기 때문.
밑에 내용을 기억해두자

인덱스로 데이터에 접근하고 끝에 삽입, 삭제만 할 경우에는 ArrayList를 사용하자.
stack, queue 혹은 deque로 사용한다면 ArrayDeque를 사용하자.
리스트를 순회할때 삽입, 삭제 빈번하다면 LinkedList를 사용하자.
참고한 블로그

✅ 2️⃣ Pair 객체를 사용하여 가독성 향상

• int[] 배열 대신 Pair 클래스를 사용하면 가독성이 좋아짐.

class Pair {
    int x, y;
    Pair(int x, int y) { this.x = x; this.y = y; }
}

🔽 개선 코드

Queue<Pair> queue = new ArrayDeque<>();
queue.add(new Pair(x, y));

---

🔥 시간 복잡도 분석

• 격자 크기: N x N (최대 100 x 100 = 10,000)
• BFS 탐색: O(N^2)
• 각 노드는 4번 방문할 수 있음 (최대 4N^2 연산) → O(N^2)
• 최악의 경우 10000 * 4 = 40000 연산이므로 충분히 해결 가능!

---

🎯 결론

✅ BFS를 사용하여 효율적으로 얼음 덩어리를 탐색
✅ 방문 처리를 개선하여 불필요한 연산 최소화
✅ Queue 대신 Deque, Pair 사용으로 가독성 및 메모리 최적화
✅ 시간 복잡도 O(N^2), 충분히 해결 가능! 🚀

---

🔹 **배운 점**
- BFS는 **연결된 영역 탐색**에 유용하다!
- 방문 처리는 **Queue에 추가될 때 즉시 처리**하는 것이 최적화됨.
- `ArrayDeque`가 `LinkedList`보다 **메모리 효율성이 좋음**.