[BOJ] 백준 3184 - 양 풀이

1. 문제

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

3184번: 양

 

2. 풀이

백준 실버 1의 DFS 문제이다.
첫 번째 줄의 입력을 받아 R, C를 초기화하고 map 선언한 후 마당의 각 줄의 정보를 입력받아 배열을 초기화한다.
그 후 방문 배열을 선언 및 초기화하고 한 칸에서 수평, 수직으로만 이동할 수 있다고 제시했으므로 행과 열은 1씩 이동이 가능하다는 이야기 이다. 따라서 이동할 좌표를 선택할 수 있는 dx, dy 배열도 그에 맞게 선언해준다.

그 후 map 2차원 배열을 이중 반복문을 통해 탐색하는데 이때 방문했거나 현재의 좌표가 울타리('#')면 탐색하지 않는다.
탐색할때는 dfs_sheep_wolf 함수로 현재 탐색하고자 하는 좌표를 파라미터로 보낸다. 함수에서는 우선 방문했으므로 방문 처리(true)를 해주고 현재 탐색한 좌표의 map 값이 양이면(o) 양의 숫자(sheepCnt)를 +1 해주고 늑대면(v) 늑대의 숫자(wolfCnt)를 +1 해준다. 
이제 넘겨받은 파라미터에 dx, dy를 더해주고 그 값이 map의 범위를 넘지 않는다면 상하좌우를 각각 재귀적으로 탐색하면서 양의 숫자와 늑대의 숫자를 카운트한다. 

하나의 좌표에 대해 탐색이 끝나면 다시 main의 map 2차원 배열 이중 반복문으로 돌아와서 카운트한 양의 숫자가 늑대의 숫자보다 크다면 늑대의 숫자를 0으로 만들고 카운트한 늑대의 숫자가 양의 숫자보다 크다면 양의 숫자를 0으로 만든 후 양의 숫자 결과(sheepCntResult)와 늑대의 숫자 결과(wolfCntResult)에 각각 더해주고 양의 숫자와 늑대의 숫자를 다시 카운트 해야 하므로 0으로 만들어준다.

마지막으로 양의 숫자 결과(sheepCntResult)와 늑대의 숫자 결과(wolfCntResult)를 출력해주면 정답!!

 

3. 소스 코드

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

public class Main {
    static char[][] map;
    static int R, C;

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

    static int sheepCnt = 0;
    static int wolfCnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new char[R][C];
        for (int i = 0; i < R; i++) {
            String input = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = input.charAt(j);
            }
        }
        visited = new boolean[R][C];

        int sheepCntResult = 0;
        int wolfCntResult = 0;

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] != '#' && !visited[i][j]) {
                    dfs_sheep_wolf(i, j);

                    if (sheepCnt > wolfCnt) {
                        wolfCnt = 0;
                    } else {
                        sheepCnt = 0;
                    }

                    sheepCntResult += sheepCnt;
                    wolfCntResult += wolfCnt;

                    sheepCnt = 0;
                    wolfCnt = 0;
                }
            }
        }

        bw.write(Integer.toString(sheepCntResult) + " " + Integer.toString(wolfCntResult));
        bw.flush();
        bw.close();
        br.close();
    }

    private static void dfs_sheep_wolf(int x, int y) {
        visited[x][y] = true;

        if (map[x][y] == 'o') {
            sheepCnt += 1;
        } else if (map[x][y] == 'v') {
            wolfCnt += 1;
        }

        for (int i = 0; i < 4; i++) {
            int xf = x + dx[i];
            int yf = y + dy[i];

            if (xf >= 0 && xf < R && yf >= 0 && yf < C && !visited[xf][yf] && map[xf][yf] != '#') {
                dfs_sheep_wolf(xf, yf);
            }
        }
    }
}