[BOJ] 3184 양, 3187 양치기 꿍

양
양치기꿍

(두개 풀이가 같음)

풀이

• 울타리(#) 이 아닌 곳을 만났을 때 bfs 또는 dfs를 실행하여 각 구역을 탐색함.
• dfs가 실행속도 더 빠름
• 전역변수로 각 구역의 w_cnt(늑대수),s_cnt(양의수) 를 선언 후, bfs 내에서 cnt를 셈.
• bfs 실행 뒤, 구역 내의 양의 수가 많으면 총 양의 수인 s_ans에 그 구역의 양의 수를 더해주고, 아니라면 총 늑대의 수인 w_ans 에 구역의 늑대의 수를 더해줌

코드

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

public class BOJ3184 {
    
    static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static char[][] map;
    static boolean[][] visited;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
    static int w_cnt, s_cnt;
    static int w_ans=0, s_ans=0;
    static int R, C;

    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        visited = new boolean[R][C];
        
        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
        }
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] != '#' && !visited[i][j]) {
                    w_cnt = 0; //늑대 갯수
                    s_cnt = 0; //양 갯수
                    bfs(i, j);
                    //dfs(i,j);
                    if (s_cnt > w_cnt) {
                        s_ans += s_cnt;
                    } else {
                        w_ans += w_cnt;
                    }
                }
            }
        }
        System.out.println(s_ans+" "+w_ans);
    }

	private static void dfs(int x, int y) {
        visited[x][y] = true;
        if (map[x][y] == 'o') {
            s_cnt++;
        }
        else if (map[x][y] == 'v') {
            w_cnt++;
        }
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && xx < R && yy >= 0 && yy < C && map[xx][yy] != '#' && !visited[xx][yy])
                dfs(xx, yy);
        }
    }
    
    private static void bfs(int x, int y) {
        visited[x][y] = true;
        Queue<Point> queue = new LinkedList<>();
        
        if (map[x][y] == 'o') {
            s_cnt++;
        }
        else if (map[x][y] == 'v') {
            w_cnt++;
        }
        queue.offer(new Point(x, y));

        while (!queue.isEmpty()) {
            Point cur = queue.poll();
            for (int i = 0; i < 4; i++) {
                int xx = cur.x + dx[i];
                int yy = cur.y + dy[i];

                if (xx >= 0 && xx < R && yy >= 0
                && yy < C && map[xx][yy] != '#' && !visited[xx][yy]) 
                {
                    visited[xx][yy] = true;
                    if (map[xx][yy] == 'o') {
                        s_cnt++;
                        queue.offer(new Point(xx, yy));
                    }
                    else if (map[xx][yy] == 'v') {
                        w_cnt++;
                        queue.offer(new Point(xx, yy));
                    }
                    else {
                         queue.offer(new Point(xx, yy));
                    }
                }
            }

        }
    }
}