# 유형 : 그래프 탐색, BFS
# 난이도 : 실버 2
# 울타리로 구분되어있는 부분을 BFS탐색을 돌리며 양과 늑대의 수를 체크한 다음 계산해주면 되었던 전형적인 BFS문제
|
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
|
package bj;
import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class p3187 {
static int R,C;
static char arr[][];
static boolean visit[][];
static int moveX[] = {0,1,0,-1};
static int moveY[] = {-1,0,1,0};
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());
arr = new char[R][C];
visit = new boolean[R][C];
int sheep = 0;
int wolf = 0;
for(int r=0; r<R; r++) {
String str = br.readLine();
for(int c=0; c<C; c++) {
arr[r][c] = str.charAt(c);
}
}
for(int r=0; r<R; r++) {
for(int c=0; c<C; c++) {
if(arr[r][c] != '#' && !visit[r][c]) {
Point po = bfs(r,c);
wolf += po.x;
sheep += po.y;
}
}
}
System.out.println(sheep +" " +wolf);
}
private static Point bfs(int row, int col) {
// TODO Auto-generated method stub
Queue<Point> queue = new LinkedList<Point>();
visit[row][col] = true;
queue.add(new Point(col, row));
int sheep = 0;
int wolf = 0;
while(!queue.isEmpty()) {
Point po = queue.poll();
if(arr[po.y][po.x] == 'v')
wolf++;
else if(arr[po.y][po.x] == 'k')
sheep++;
for(int d=0; d<4; d++) {
int newY = po.y + moveY[d];
int newX = po.x + moveX[d];
if(0<=newY && newY<R && 0<=newX && newX<C && !visit[newY][newX] && arr[newY][newX] != '#') {
visit[newY][newX] = true;
queue.add(new Point(newX, newY));
}
}
}
if(wolf>=sheep) {
sheep = 0;
}else {
wolf = 0;
}
return new Point(wolf, sheep);
}
}
|
cs |
'백준' 카테고리의 다른 글
| #백준_1614 영식이의 손가락 - Java 자바 (0) | 2020.03.04 |
|---|---|
| #백준_3006 터보소트 - Java 자바 (0) | 2020.03.03 |
| #백준_2234 성곽 - Java 자바 (0) | 2020.03.02 |
| #백준_3987 보이저 1호 - Java 자바 (0) | 2020.03.02 |
| #백준_15684 사다리 조작 - Java 자바 (0) | 2020.02.29 |