[BOJ] 3184 - 양(Java)

안녕하세요! 오늘은 대표적인 그래프 탐색(DFS/BFS) 응용 문제인 백준 3184번 '양' 문제의 풀이 과정을 공유하려고 합니다. 단순히 영역의 개수나 크기를 세는 것을 넘어, 각 영역의 구성 요소를 파악하고 비교해야 하는 흥미로운 문제였습니다. 특히 재귀 DFS를 구현하면서 겪었던 두 가지 큰 실수를 통해 많은 것을 배울 수 있었습니다.

📔문제 설명

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

이 문제는 울타리로 둘러싸인 영역 안의 양과 늑대의 수를 세고, 양이 늑대보다 많으면 늑대가 잡아먹히고, 그렇지 않으면 양이 모두 잡아먹히는 규칙을 적용하는 문제입니다. 최종적으로 살아남은 양과 늑대의 총 수를 출력해야 합니다.

---

🔍 접근법

먼저 '울타리로 나뉜 영역'이라는 점에서 그래프의 연결 요소를 찾는 문제임을 알 수 있었습니다. 따라서 각 영역을 탐색하기 위해 DFS를 사용하기로 했습니다.

한 가지 특징은, 각 영역에서 '양의 수'와 '늑대의 수'라는 두 가지 정보를 동시에 계산해야 한다는 점입니다. int 하나만 반환하는 일반적인 DFS로는 한계가 있었죠.

그래서 저는 두 값을 함께 관리하기 위해 Animal이라는 커스텀 클래스를 만들었습니다.

static class Animal{
    int wolfCnt;
    int sheepCnt;

    Animal(int wolfCnt, int sheepCnt){
        this.wolfCnt = wolfCnt;
        this.sheepCnt = sheepCnt;
    }
}

실행 과정에서는 두가지 문제를 마주했는데, 먼저 처음 작성한 dfs 코드에서 dfs(row, col)가 호출되었을 때, 정작 그 시작점인 (row, col) 위치에 있는 동물을 세지 않는 현상이 있었고, 이 때문에 영역 내 동물의 수가 계속 누락되는 문제가 발생했습니다.

이를 해결하기 위해 dfs 함수가 시작되자마자, 전달받은 (row, col) 좌표의 문자가 무엇인지 확인하고 Animal 객체의 카운트를 먼저 초기화하는 로직을 추가했습니다.

static Animal dfs(int row, int col){
    visited[row][col] = true;
		
    Animal animal = new Animal(0,0);
    
    //현재 위치에 동물이 있는 경우도 계산
    if(graph[row][col] == 'o'){
        animal.sheepCnt=1;
    }else if(graph[row][col] == 'v'){
        animal.wolfCnt=1;
    }
    
    ...
}

첫 번째 문제를 해결하고 나서도 계산이 정확하지 않았습니다. 원인은 이웃 노드를 탐색하는 switch-case 문에 있었습니다.

//기존 로직
switch(next){
    case '.':
        // 이웃이 빈 공간일 때, 그 결과를(return 값을) 받아와서 더해주지 않고 버림
        dfs(newX, newY);
        break;
    case 'o':
        // 이웃이 양일 때, 그 너머 영역에 있는 '양'의 수만 더하고 '늑대'의 수는 무시
        animal.sheepCnt+=dfs(newX,newY).sheepCnt;
        break;
    case 'v':
        // 이웃이 늑대일 때, 그 너머 영역에 있는 '늑대'의 수만 더하고 '양'의 수는 무시
        animal.wolfCnt+=dfs(newX,newY).wolfCnt;
  break;
}

기존의 잘못된 로직은 이웃 노드의 종류에 따라 합산 방식을 다르게 적용하여 문제가 발생했습니다. 이웃이 빈 공간이면 그 너머 영역의 동물 수를 전부 무시했고, 양이나 늑대인 경우에도 각각 늑대나 양의 수를 누락한 채 반쪽짜리 정보만 더했습니다. 이처럼 재귀 호출로 얻은 결괏값을 온전히 합산하지 않았기 때문에, 영역 전체의 정확한 동물 마릿수를 계산할 수 없었습니다.

이를 해결하기 위해 이웃이 방문 가능한 곳이라면, 종류에 상관없이 무조건 dfs를 호출해서 그 영역의 Animal 객체를 통째로 받아와서 값을 업데이트 해줬습니다.

//수정 후

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

      if(rangeCheck(newX, newY) && !visited[newX][newY]){
          // 이웃이 무엇이든 상관없이, 일단 탐색하고 결과를 통째로 받아온다.
          Animal next = dfs(newX, newY);
          
          // 받아온 결과의 양과 늑대 수를 모두 현재 카운트에 더해준다.
          animal.sheepCnt+=next.sheepCnt;
          animal.wolfCnt+=next.wolfCnt;
      }
}

---

💻 코드

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

public class Main {
    static int R, C;
    static char[][] graph;
    static boolean[][] visited;

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

    static int totalSheepCnt = 0;
    static int totalWolfCnt = 0;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        graph = new char[R][C];
        visited = new boolean[R][C];

        for(int i=0; i<R; i++){
            String s = br.readLine();
            for(int j=0; j<C; j++){
                graph[i][j] = s.charAt(j);
            }
        }

        for(int i=0; i<R; i++){
            for(int j=0; j<C; j++){
                if(!visited[i][j] && graph[i][j] != '#'){
                    Animal animal = dfs(i,j);

                    if(animal.sheepCnt > animal.wolfCnt){
                        totalSheepCnt+=animal.sheepCnt;
                    }else if(animal.sheepCnt <= animal.wolfCnt){
                        totalWolfCnt+=animal.wolfCnt;
                    }
                }
            }
        }

        System.out.println(totalSheepCnt + " " + totalWolfCnt);
    }

    static Animal dfs(int row, int col){
        visited[row][col] = true;

        Animal animal = new Animal(0,0);
        if(graph[row][col] == 'o'){
            animal.sheepCnt=1;
        }else if(graph[row][col] == 'v'){
            animal.wolfCnt=1;
        }

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

            if(rangeCheck(newX, newY) && !visited[newX][newY]){
                Animal next = dfs(newX, newY);
                animal.sheepCnt+=next.sheepCnt;
                animal.wolfCnt+=next.wolfCnt;
            }
        }
        return animal;
    }

    static class Animal{
        int wolfCnt;
        int sheepCnt;

        Animal(int wolfCnt, int sheepCnt){
            this.wolfCnt = wolfCnt;
            this.sheepCnt = sheepCnt;
        }
    }

    static boolean rangeCheck(int row, int col){
        return row>=0 && col>=0 && row<R && col<C && graph[row][col] != '#';
    }
}

---

💡 마무리

1. 재귀 함수는 '자기 자신'의 일을 먼저 처리해야 한다: 함수가 호출된 그 시점의 노드에 대한 처리를 명확히 하는 것이 모든 재귀의 시작입니다.
2. 결과의 합산은 일관되어야 한다: 이웃의 상태에 따라 로직을 다르게 하는 것이 아니라, '그 너머 영역의 총합'이라는 일관된 결과를 받아와 합산하는 것이 훨씬 간단하고 강력한 방법입니다.

단순히 문제를 푸는 것을 넘어, 실수를 통해 더 견고한 로직을 배워나가는 과정이 즐거웠던 문제였습니다.

---