백준 3187. 양치기 꿍 :: 돼지개발자

출처 : https://www.acmicpc.net/problem/3187

"BFS 탐색"

해당 문제는 울타리로 나눠진 구역 안에 양과 늑대에 수에 따라 늑대가 죽는지 양이 죽는지 판별하는 문제로 단지영역나누기 와 비슷한 문제이다. 따라서 BFS 탐색으로 울타리가 아닌 지점을 모두 탐색하여 영역 내 양과 늑대의 수를 파악하고, 그 결과에 따라 양 > 늑대 이면 늑대를 죽이고, 양 <= 늑대 이면 양을 죽인다. 

방문한 곳을 또 방문하면 안되므로 visited 배열을 사용했음을 확인한다.

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 Main {
 
    static int R,C;
    static char[][]map;
    static boolean[][] visited;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static int sheep;
    static int wolf;
    static Queue<Node> q = new LinkedList<>();
    
    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());
        
        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]) continue;
                solve(i,j);
            }
        }
        System.out.println(sheep+" "+wolf);
    }
    
    static void solve(int x, int y) {
        int v = 0;
        int k = 0;
        visited[x][y] = true;
        q.add(new Node(x, y));
        
        while(!q.isEmpty()) {
            
            Node cur = q.poll();
 
            if(map[cur.x][cur.y] == 'v') v++;
            if(map[cur.x][cur.y] == 'k') k++;
            
            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                
                if(!isRange(nx, ny) || visited[nx][ny] || map[nx][ny] == '#')
                    continue;
                
                visited[nx][ny] = true;
                q.add(new Node(nx, ny));
            }
        }
        
        if(v >= k) {
            wolf += v;
        }
        else {
            sheep +=k;
        }
        
    }
    
    static boolean isRange( int x, int y) {
        if( x < 0 || x>= R || y <0 || y >=C) return false;
        return true;
    }
}
 
class Node {
    int x;
    int y;
    
    Node(int x,int y) {
        this.x = x;
        this.y = y;
    }
}