[백준 / Java] 3184: 양 (BFS)

난이도: Silver 1

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

 

문제

미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다.

마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다.

한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서 "탈출"할 수 있는 칸은 어떤 영역에도 속하지 않는다고 간주한다.

다행히 우리의 양은 늑대에게 싸움을 걸 수 있고 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아낸다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.

맨 처음 모든 양과 늑대는 마당 안 영역에 존재한다.

아침이 도달했을 때 살아남은 양과 늑대의 수를 출력하는 프로그램을 작성하라.

입력

첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다.

다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다.

출력

하나의 줄에 아침까지 살아있는 양과 늑대의 수를 의미하는 두 정수를 출력한다.

---

 

2차원 배열 BFS 알고리즘의 기본 문제이다.

기본적으로 문제에서 주어진 배열을 입력받을 2차원 배열 yard를 선언하고,

방문 체크를 할 2차원 배열 visited를 선언하고, 

살아있는 양의 수와 살아있는 늑대의 수를 저장할 livenSheep, livenWolf 변수를 선언한다.

 

전체 2중 for문을 돌리면서,

해당 칸을 방문하지 않았고 해당 칸이 '#'(울타리)가 아닐 때는 bfs 메서드에 인수로  i, j를 넘겨주면 된다.

이렇게 함으로써 bfs를 수행하는 메서드는 울타리 안에 있는 구역만 돌게 된다.

 

bfs 메서드 내에서는 따로 sheep, wolf 변수를 선언하고

접근한 칸이 'o'이면 sheep 변수를 1 증가시키고, 접근한 칸이 'v'이면 wolf 변수를 1 증가시킨다.

그리고 최종적으로 sheep 변수의 값이 wolf 변수의 값보다 크면 livenSheep 변수에 sheep 변수의 값을 모두 더하고,

그 외의 경우에는 livenWolf 변수에 wolf 변수의 값을 모두 더한다.

 

코드에 적힌 주석을 보면 바로 이해가 될 것이다.

자, 이제 코드를 보자.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class P3184_양 {
    static int R, C;                    // 마당의 가로, 세로 크기
    static int[] dx = {-1, 0, 1, 0};    // 상, 하 이동
    static int[] dy = {0, -1, 0, 1};    // 좌, 우 이동
    static char[][] yard;                // 2차원 마당 배열
    static boolean[][] visited;            // 2차원 방문 배열
    static int livenSheep, livenWolf;    // 살아있는 양의 수, 살아있는 늑대의 수
    
    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());
        yard = new char[R][C];            // 마당 배열 크기 지정
        visited = new boolean[R][C];    // 방문 배열 크기 지정
        
        // 2차원 마당 배열 초기화
        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                // '.': 빈 필드
                // '#': 울타리
                // 'o': 양
                // 'v': 늑대
                yard[i][j] = line.charAt(j);
            }
        }
        
        // 모든 칸 탐색
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                // 해당 칸을 방문하지 않았고, 울타리가 아니라면 새로운 구역 발견
                if (!visited[i][j] && yard[i][j] != '#') {
                    bfs(i, j);    // 해당 칸부터 bfs 수행
                }
            }
        }
        
        // 살아있는 양과 살아있는 늑대의 수 출력
        System.out.println(livenSheep + " " +  livenWolf);
    }
    
    public static void bfs(int x, int y) {
        Queue<Point> queue = new LinkedList<>();    // bfs 수행을 위한 큐
        int sheep = 0;    // 이 구역 양의 수
        int wolf = 0;    // 이 구역 늑대의 수
        
        queue.add(new Point(x, y));        // 큐에 시작 칸 삽입
        visited[x][y] = true;            // 시작 칸을 방문 체크
        
        if (yard[x][y] == 'o') {        // 시작 칸에 양이 있다면
            sheep++;    // 이 구역 양의 수 1 증가
        } else if (yard[x][y] == 'v') {    // 시작 칸에 늑대가 있다면    
            wolf++;        // 이 구역 늑대의 수 1 증가
        }
        
        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            Point now = queue.poll();    // 현재 칸을 큐에서 뽑기
            
            // 현재 칸 기준으로 상, 하, 좌, 우 탐색
            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];        // 인접 칸의 x좌표
                int ny = now.y + dy[i];        // 인접 칸의 y좌표
                
                // 인접 칸의 x좌표나 y좌표가 유효한 인덱스 범위가 아니라면 건너뛰기
                if (nx < 0 || ny < 0 || nx >= R || ny >= C) {
                    continue;
                }
                
                // 인접 칸을 이미 방문했거나, 인접 칸이 울타리라면 건너뛰기
                if (visited[nx][ny] || yard[nx][ny] == '#') {
                    continue;
                }
                
                queue.add(new Point(nx, ny));    // 큐에 인접 칸 삽입
                visited[nx][ny] = true;            // 인접 칸을 방문 체크
                
                if (yard[nx][ny] == 'o') {        // 인접 칸에 양이 있다면
                    sheep++;    // 이 구역 양의 수 1 증가
                } else if (yard[nx][ny] == 'v') {    // 인접 칸에 늑대가 있다면
                    wolf++;        // 이 구역 늑대의 수 1 증가
                }
            }
        }
        
        if (sheep > wolf) {
            // 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아낸다. 
            // => 살아있는 양의 수에 이 구역 양의 수를 모두 더하기
            livenSheep += sheep;
        } else {    
            // 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.
            // => 살아있는 늑대의 수에 이 구역 늑대의 수를 모두 더하기
            livenWolf += wolf;
        }
    }
    
    static class Point {
        int x, y;
        
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}