BOJ::문제풀이

3187 양치기 꿍

2영재 2018. 1. 6. 02:21

BOJ::3187 양치기 꿍

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


울타리 부분을 제외하고 dfs로 탐색하면서 양과 늑대의 수를 카운팅하고

조건에 맞춰 하나를 0으로 만들고 결과에 누적시키면 된다.


<JAVA>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    
    static final int SZ = 251;
    static final int dx[] = {0,0,1,-1};
    static final int dy[] = {1,-1,0,0};
    
    static int map[][]= new int[SZ][SZ];
    static boolean check[][] = new boolean[SZ][SZ];
    static int r, c, result_wolf, result_sheep;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        r = sc.nextInt();
        c = sc.nextInt();
        
        for(int i = 0 ; i < r ; i++){
            String buf = sc.next();
            for(int j = 0 ; j < c ; j++){
                map[i][j] = buf.charAt(j);
            }
        }
        
        //printMap();
        
        result_wolf = 0;
        result_sheep = 0;
        
        for(int i = 0 ; i < r ; i++){
            for(int j = 0 ; j < c ; j++){
                //울타리가 아니고 방문하지 않았으면 탐색 시작
                if(check[i][j] == false && map[i][j] != '#'){
                    //탐색
                    bfs(i, j);
                }
            }
        }
        
        System.out.println(result_sheep + " " + result_wolf);
    }
    
    public static void bfs(int a, int b){
        Queue<Node> q = new LinkedList();
        q.add(new Node(a, b));
        check[a][b]=true;
        
        int wolf_count = 0;
        int sheep_count = 0;
        
        while(!q.isEmpty()){
            int x = q.peek().x;
            int y = q.poll().y;
            
            if(map[x][y] == 'v') wolf_count++;
            if(map[x][y] == 'k') sheep_count++;
            
            for(int i = 0 ; i < 4; i++){
                int ax = x + dx[i];
                int ay = y + dy[i];
                if(ax>=0&&ay>=0&&ax<r&&ay<c){
                    if(map[ax][ay] != '#' && check[ax][ay] == false){
                        check[ax][ay]=true;
                        q.add(new Node(ax,ay));
                    }
                }
            }
        }
        
        if(sheep_count > wolf_count){
            result_sheep += sheep_count;
        }else{
            result_wolf += wolf_count;
        }
    }
    
    public static void printMap(){
        for(int i= 0 ; i < r ; i++){
            for(int j = 0 ; j < c ; j++){
                System.out.print((char)map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
    
}
 
class Node{
    int x, y;
    Node(int x,int y){
        this.x = x;
        this.y = y;
    }
}
 
cs


저작자표시