[JAVA]백준 3184번: 양

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

3184번: 양

1. 문제 설명

 

문제

• 미키의 뒷마당이 주어진다.
• 마당은 행과 열로 이루어진 직사각형 모양이며, #은 울타리, o는 양, v는 늑대를 의미한다.
• 수평, 수직으로만 이동해서 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다.
• 마당에서 "탈출"할 수 있는 칸은 영역에 속하지 않는다.
• 영역 안의 양의 수가 늑대의 수보다 많으면 양이 이겨 늑대를 쫓아내고, 그렇지 않다면 늑대가 양을 다 잡아먹는다.
• 맨 처음 모든 양과 늑대는 마당 안의 영역에 존재한다.
• 아침이 되었을 때 살아남은 양과 늑대의 수를 출력

조건

• 행 R, 열 C (3 <=R, C <=250)

 

2. 풀이

 

DFS로 풀 수 있는 문제이다.

 

마당에서 이전에 처리하지 않은 양 또는 늑대를 발견할 경우 그 시점(x, y)부터 탐색을 시작해나가서 그 영역의 모든 양과 늑대의 개수를 구한다.

 

그 후, 양의 개수가 더 많으면 총 양의 개수에 더해주고, 늑대의 개수가 더 많거나 같으면 총늑대의 개수에 더해준다.

 

문제 조건에서 "맨 처음 모든 양과 늑대는 마당 안의 영역에 존재한다"라고 하여 이렇게 간단하게 풀 수 있었다.

 

만약, 이 조건이 없다면, 양과 늑대가 마당에서 "탈출"할 수 있는 칸에 있을 수 있다. 즉 양과 늑대가 마당 안의 영역에 존재하지 않을 수도 있다.

 

그럴 경우, 탐색 중 마당의 영역 밖으로 나가게 될 때를 구분해주는 구현을 추가하면 풀 수 있을 것 같다.

 

 

*로직

1. 방문하지 않았으면서, 양과 늑대가 있는 경우 dfs 탐색 시작

2. 다음 가려고 하는 위치가 마당을 벗어나지 않으면서, 울타리가 아니고, 방문하지 않을 경우 탐색을 계속한다.

3. 탐색 종료 후, 양과 늑대의 개수를 비교해서 답을 구해나간다.

 

3. 코드

// JAVA 11 , 메모리 : 16332KB, 시간 : 160ms

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

public class Main {

    public static int height, width;
    public static char[][] garden;
    public static boolean[][] visited;
    public static int[][] move = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    public static int sheep=0, wolf = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int answerSheep = 0, answerWolf = 0;

        StringTokenizer st = new StringTokenizer(br.readLine());

        height = Integer.parseInt(st.nextToken());
        width = Integer.parseInt(st.nextToken());

        garden = new char[height][width];
        visited = new boolean[height][width];

        for (int x = 0; x < height; x++) {
            garden[x] = br.readLine().toCharArray();
        }

        // 방문하지 않은, 양과 늑대가 발견된다면 탐색 시작
        for (int x = 0; x < height; x++) {
            for (int y = 0; y < width; y++) {
                if (!visited[x][y] && (garden[x][y] == 'o' || garden[x][y] == 'v')) {
                    sheep = wolf = 0;
                    dfs(x, y);
                    // 양이 더 많을 경우 양이 이긴다.
                    if(sheep>wolf)
                        answerSheep += sheep;
                    else
                        answerWolf += wolf;
                }
            }
        }

        sb.append(answerSheep).append(" ").append(answerWolf);

        System.out.println(sb);


    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;

        // 양이나 늑대일 경우 횟수 증가
        if(garden[x][y]=='v')
            wolf++;
        if(garden[x][y]=='o')
            sheep++;

        int next_x, next_y;

        for (int i = 0; i < 4; i++) {
            next_x = x + move[i][0];
            next_y = y + move[i][1];

            // 범위를 벗어나거나, 방문한적이 있거나, 울타리일 경우 탐색하지 않는다.
            if(next_x<0 || next_y<0 || next_x>=height || next_y>=width || visited[next_x][next_y] || garden[next_x][next_y]=='#')
                continue;

            visited[next_x][next_y] = true;
            dfs(next_x, next_y);
        }
    }

}