[BOJ/Java] 양치기 꿍 (3187)

양치기 꿍 (3187)

1. 문제 분석

문제 개요

• 양치기 꿍은 마당에서 양과 늑대가 몇 마리 있는지 확인하고자 한다.
• 주어진 마당에서 "양"과 "늑대"가 각각 살아남을 수 있는 영역을 확인해야 한다.
• 양과 늑대는 #으로 막힌 울타리로 둘러싸인 공간에서만 서로 영향을 주고받으며, 영역 안에서 양이 늑대보다 많으면 늑대가 모두 쫓겨나고, 그렇지 않으면 양이 모두 잡아먹힌다.

입력 형식

• 첫째 줄에 두 정수 R과 C가 주어진다. (3 ≤ R, C ≤ 250)
• 다음 R개의 줄에는 C개의 문자로 이루어진 마당의 모양이 주어진다.
  • '.'는 빈 필드
  • '#'는 울타리
  • 'k'는 양
  • 'v'는 늑대

출력 형식

• 최종적으로 살아남는 양과 늑대의 수를 출력한다.

2. 알고리즘 종류

• 이 문제는 그래프 탐색 문제로, 울타리 #로 구분된 영역 내에서 각각의 양과 늑대의 수를 세어야 한다.
• 깊이 우선 탐색 (DFS) 또는 너비 우선 탐색 (BFS)를 사용하여 연결된 영역을 탐색하며 양과 늑대의 수를 계산한다.

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

1. 입력 처리 및 초기화

• 입력을 통해 마당의 크기와 모양을 저장하고, 방문 여부를 확인할 visited 배열을 초기화한다.

2. 각 영역 탐색 및 양, 늑대 수 계산

• 마당 전체를 순회하며 울타리가 아니고 방문하지 않은 곳을 발견하면, DFS를 통해 해당 영역을 탐색하고 양과 늑대의 수를 계산한다.
• 각 영역 탐색이 완료되면 양과 늑대의 수를 비교하여 최종 결과에 반영한다.

4. 코드 설명

(1) 메인 함수 (main)

• 입력 처리 및 초기화

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 객체 생성
    StringTokenizer st = new StringTokenizer(br.readLine()); // 첫 번째 줄 입력 처리
    R = Integer.parseInt(st.nextToken()); // 마당의 행 수 R 입력
    C = Integer.parseInt(st.nextToken()); // 마당의 열 수 C 입력
    field = new String[R][C]; // 마당을 저장할 2차원 배열 생성
    visited = new boolean[R][C]; // 방문 여부를 체크할 2차원 배열 생성
  
    for (int i = 0; i < R; i++) field[i] = br.readLine().split(""); // 마당의 각 행을 입력받아 저장

  • BufferedReader와 StringTokenizer를 사용하여 입력을 처리하고, 마당의 크기에 맞게 배열을 초기화한다.

• 각 영역 탐색 및 결과 계산

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (field[i][j].equals("#") || visited[i][j]) continue; // 울타리이거나 방문한 곳은 무시
            sheepCnt = 0; wolfCnt = 0; // 양과 늑대의 수를 초기화
            dfs(i, j); // 해당 위치에서 DFS 탐색 시작
            if (sheepCnt > wolfCnt) sheepAnswer += sheepCnt; // 양이 더 많으면 양의 수를 결과에 추가
            else wolfAnswer += wolfCnt; // 그렇지 않으면 늑대의 수를 결과에 추가
        }
    }
    System.out.println(sheepAnswer + " " + wolfAnswer); // 최종 결과 출력

  • 마당 전체를 순회하며 울타리가 아니고 방문하지 않은 곳에서 DFS를 호출하여 탐색을 시작한다.
  • 탐색이 완료되면 각 영역의 양과 늑대의 수를 비교하여 최종 결과를 갱신한다.

(2) 깊이 우선 탐색 함수 (dfs)

• DFS를 이용하여 연결된 영역 탐색 및 양, 늑대 수 계산

    public static void dfs(int r, int c) {
        visited[r][c] = true; // 현재 위치를 방문 처리
        if (field[r][c].equals("v")) wolfCnt++; // 늑대일 경우 늑대 수 증가
        else if (field[r][c].equals("k")) sheepCnt++; // 양일 경우 양 수 증가
        for (int i = 0; i < 4; i++) { // 상하좌우 4방향 탐색
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 || nc < 0 || nr >= R || nc >= C || visited[nr][nc] || field[nr][nc].equals("#")) continue; // 경계 검사 및 방문 여부 확인
            visited[nr][nc] = true; // 다음 위치를 방문 처리
            dfs(nr, nc); // 재귀 호출을 통해 다음 위치 탐색
        }
    }

  • 현재 위치를 방문 처리한 후, 해당 위치가 양인지 늑대인지 확인하여 카운트를 증가시킨다.
  • 상하좌우 4방향을 검사하며 유효한 위치로 재귀 호출을 통해 탐색을 진행한다.

5. 전체 코드

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

public class BOJ3187 {
    static int R, C, sheepCnt, wolfCnt, sheepAnswer = 0, wolfAnswer = 0;
    static String[][] field; // 마당을 나타내는 2차원 배열
    static boolean[][] visited; // 방문 여부를 체크할 2차원 배열
    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 객체 생성
        StringTokenizer st = new StringTokenizer(br.readLine()); // 첫 번째 줄 입력 처리
        R = Integer.parseInt(st.nextToken()); // 마당의 행 수 R 입력
        C = Integer.parseInt(st.nextToken()); // 마당의 열 수 C 입력
        field = new String[R][C]; // 마당을 저장할 2차원 배열 생성
        visited = new boolean[R][C]; // 방문 여부를 체크할 2차원 배열 생성

        for (int i = 0; i < R; i++) field[i] = br.readLine().split(""); // 마당의 각 행을 입력받아 저장

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (field[i][j].equals("#") || visited[i][j]) continue; // 울타리이거나 방문한 곳은 무시
                sheepCnt = 0; wolfCnt = 0; // 양과 늑대의 수를 초기화
                dfs(i, j); // 해당 위치에서 DFS 탐색 시작
                if (sheepCnt > wolfCnt) sheepAnswer += sheepCnt; // 양이 더 많으면 양의 수를 결과에 추가
                else wolfAnswer += wolfCnt; // 그렇지 않으면 늑대의 수를 결과에 추가
            }
        }
        System.out.println(sheepAnswer + " " + wolfAnswer); // 최종 결과 출력
    }

    public static void dfs(int r, int c) {
        visited[r][c] = true; // 현재 위치를 방문 처리
        if (field[r][c].equals("v")) wolfCnt++; // 늑대일 경우 늑대 수 증가
        else if (field[r][c].equals("k")) sheepCnt++; // 양일 경우 양 수 증가
        for (int i = 0; i < 4; i++) { // 상하좌우 4방향 탐색
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 || nc < 0 || nr >= R || nc >= C || visited[nr][nc] || field[nr][nc].equals("#")) continue; // 경계 검사 및 방문 여부 확인
            visited[nr][nc] = true; // 다음 위치를 방문 처리
            dfs(nr, nc); // 재귀 호출을 통해 다음 위치 탐색
        }
    }
}