[BOJ/Java] 양 한마리... 양 두마리... (11123)

양 한마리... 양 두마리... (11123)

1. 문제 분석

문제 개요

• 주어진 격자(grid)에서 양('#')들이 서로 연결된 덩어리의 개수를 구하는 문제이다. 양의 덩어리는 4방향(상하좌우)으로 연결된 양들을 의미한다. DFS(깊이 우선 탐색)를 사용하여 각 양의 덩어리를 탐색하고, 그 개수를 세는 것이 목표이다.

입력 형식

• 첫 번째 줄에 테스트 케이스의 개수 T가 주어진다.
• 각 테스트 케이스에 대해 첫 줄에는 격자의 높이 H와 너비 W가 주어진다.
• 이후 H줄에 걸쳐 각 줄에는 W개의 문자가 주어지며, 양은 '#'로, 빈 칸은 '.'으로 표시된다.

출력 형식

• 각 테스트 케이스에 대해 양의 덩어리 개수를 출력한다.

2. 알고리즘 종류

• DFS (깊이 우선 탐색)
  DFS를 사용하여 각 양의 덩어리를 탐색한다. 방문한 양은 visited 배열에 표시하며, 덩어리를 찾을 때마다 개수를 증가시킨다.

3. 주요 부분 및 코드 작성 방법

1. 격자 및 방문 배열 초기화

• 입력된 격자의 정보를 저장하고, 방문 여부를 기록할 visited 배열을 초기화한다.

2. DFS를 이용한 덩어리 탐색 및 결과 출력

• DFS를 사용하여 양의 덩어리를 탐색하며, 새로운 덩어리를 발견할 때마다 그 개수를 증가시킨다.

4. 코드 설명

(1) 메인 함수 (main)

• 입력 처리 및 격자 초기화

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 객체 생성
    int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수 입력
  
    for(int tc = 1; tc <= T; tc++) { // 각 테스트 케이스에 대해 반복
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        H = Integer.parseInt(st.nextToken()); // 격자의 높이
        W = Integer.parseInt(st.nextToken()); // 격자의 너비
        grid = new String[H][W]; // 격자를 저장할 배열
        visited = new boolean[H][W]; // 방문 여부를 기록할 배열
  
        for (int i = 0; i < H; i++) grid[i] = br.readLine().split(""); // 격자 정보 입력
  
        int cnt = 0; // 양의 덩어리 수 초기화
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (grid[i][j].equals("#") && !visited[i][j]) { // 양이 있고 방문하지 않았다면
                    dfs(i, j); // DFS로 해당 덩어리 탐색
                    cnt++; // 덩어리 수 증가
                }
            }
        }
        System.out.println(cnt); // 결과 출력
    }

  • 격자의 정보를 입력받아 저장하고, DFS를 통해 각 양의 덩어리를 탐색하여 그 개수를 출력한다.

(2) DFS 함수 (dfs)

• DFS 탐색 및 방문 처리

    public static void dfs(int r, int c) {
        visited[r][c] = true; // 현재 위치를 방문 처리
        for (int i = 0; i < 4; i++) { // 상하좌우 4방향으로 이동
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 || nc < 0 || nr >= H || nc >= W || visited[nr][nc]) continue; // 범위를 벗어나거나 이미 방문한 경우 건너뜀
            if (grid[nr][nc].equals("#")) { // 양이 있는 경우
                visited[nr][nc] = true; // 방문 처리
                dfs(nr, nc); // 재귀적으로 DFS 호출
            }
        }
    }

  • 현재 위치에서 시작하여 연결된 모든 양들을 탐색하며, 방문한 위치는 visited 배열에 기록한다.

5. 전체 코드

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

public class BOJ11123 {
    static int H, W; // 격자의 높이와 너비
    static String[][] grid; // 격자 정보
    static boolean[][] visited; // 방문 여부 기록
    static int[] dr = {-1, 1, 0, 0}; // 상하좌우 이동을 위한 행 변화량
    static int[] dc = {0, 0, -1, 1}; // 상하좌우 이동을 위한 열 변화량

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 객체 생성
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수 입력

        for(int tc = 1; tc <= T; tc++) { // 각 테스트 케이스에 대해 반복
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            H = Integer.parseInt(st.nextToken()); // 격자의 높이
            W = Integer.parseInt(st.nextToken()); // 격자의 너비
            grid = new String[H][W]; // 격자를 저장할 배열
            visited = new boolean[H][W]; // 방문 여부를 기록할 배열

            for (int i = 0; i < H; i++) grid[i] = br.readLine().split(""); // 격자 정보 입력

            int cnt = 0; // 양의 덩어리 수 초기화
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (grid[i][j].equals("#") && !visited[i][j]) { // 양이 있고 방문하지 않았다면
                        dfs(i, j); // DFS로 해당 덩어리 탐색
                        cnt++; // 덩어리 수 증가
                    }
                }
            }
            System.out.println(cnt); // 결과 출력
        }
    }

    // DFS를 이용해 양의 덩어리를 탐색하는 함수
    public static void dfs(int r, int c) {
        visited[r][c] = true; // 현재 위치를 방문 처리
        for (int i = 0; i < 4; i++) { // 상하좌우 4방향으로 이동
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 || nc < 0 || nr >= H || nc >= W || visited[nr][nc]) continue; // 범위를 벗어나거나 이미 방문한 경우 건너뜀
            if (grid[nr][nc].equals("#")) { // 양이 있는 경우
                visited[nr][nc] = true; // 방문 처리
                dfs(nr, nc); // 재귀적으로 DFS 호출
            }
        }
    }
}