[백준] 11123 양 한마리... 양 두마리... | DFS, BFS, 그래프 | 실버 Ⅱ | JAVA

📌 문제

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

 

⭐ Flood Fill 알고리즘의 동작 원리

1. 시작 지점 선택
   • 채우기를 시작할 특정 좌표를 선택합니다.
2. 연결된 영역 탐색
   • 시작 지점에서 상하좌우(또는 대각선 포함)로 연결된 영역을 탐색합니다.
   • 연결 기준은 보통 값이 동일한 셀(#, 특정 색상 등)을 말합니다.
3. 탐색 방법
   • 깊이 우선 탐색(DFS): 재귀적으로 연결된 모든 위치를 탐색.
   • 너비 우선 탐색(BFS): 큐를 사용해 연결된 모든 위치를 탐색.

 

⭐ Flood Fill의 핵심 개념

• 방문 표시
  이미 방문한 위치를 표시하여 중복 탐색을 방지합니다. 보통 별도의 배열(visited)이나 입력 데이터를 직접 수정합니다.
• 재귀 또는 큐 활용
  DFS는 재귀를, BFS는 큐를 활용해 인접한 셀들을 탐색합니다.

 

⭐ 알고리즘 및 구현 방식

1. 입력 처리
   • 테스트 케이스의 개수(T)를 입력받습니다.
   • 각 테스트 케이스에서 그리드의 높이(H)와 너비(W), 그리고 그리드 정보를 입력받습니다.
2. Flood Fill 알고리즘 사용
   • 방문 여부를 저장하는 배열을 만듭니다.
   • 그리드의 모든 위치를 순회하며, #이고 방문하지 않은 경우 DFS 또는 BFS를 수행하여 연결된 모든 양들을 탐색합니다.
   • 탐색을 시작할 때마다 "양 무리"의 개수를 증가시킵니다.
3. 출력 처리
   • 각 테스트 케이스에 대해 구한 "양 무리"의 개수를 출력합니다.

 

✅ 정답 코드

import java.util.*;

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

    static boolean[][] visited;
    static char[][] grid;
    static int h, w;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt(); // 테스트 케이스 수

        while (t-- > 0) {
            h = sc.nextInt();
            w = sc.nextInt();

            grid = new char[h][w];
            visited = new boolean[h][w];

            for (int i = 0; i < h; i++) {
                grid[i] = sc.next().toCharArray();
            }

            int sheepCount = 0; // 양 무리 개수

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (grid[i][j] == '#' && !visited[i][j]) {
                        dfs(i, j); // 연결된 양 탐색
                        sheepCount++;
                    }
                }
            }

            System.out.println(sheepCount);
        }
        sc.close();
    }

    // 깊이 우선 탐색 (DFS)
    private static void dfs(int x, int y) {
        visited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && ny >= 0 && nx < h && ny < w) {
                if (grid[nx][ny] == '#' && !visited[nx][ny]) {
                    dfs(nx, ny);
                }
            }
        }
    }
}

🗒️ 코드 설명

1. DFS 구현
   • 현재 위치를 방문 처리한 뒤, 상하좌우로 연결된 모든 #에 대해 재귀적으로 탐색합니다.
   • 탐색 중인 무리와 연결된 모든 양을 하나의 무리로 간주합니다.
2. 방문 처리
   • visited 배열을 사용해 이미 방문한 위치는 다시 탐색하지 않도록 합니다.
3. 무리 개수 증가
   • 새로운 무리(#이고 방문하지 않은 위치)를 발견할 때마다 sheepCount를 증가시킵니다.