문제풀이/백준
[백준]2636: 치즈 - JAVA
빈둥벤둥
2021. 5. 7. 15:37
[백준]2636: 치즈
2636번: 치즈
아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓
www.acmicpc.net
풀이
BFS 탐색 알고리즘을 사용하여 문제를 풀었다.
우선, 현재 치즈의 개수를 세어 준 다음 치즈 개수가 0이 아닐때까지 BFS 탐색을 하며 치즈의 개수를 줄여나갔다. 탐색은 0,0부터 시작하여 치즈를 만나면 해당 치즈를 없애주고, 치즈가 아니라면 큐에 넣어 근처에 있는 치즈를 탐색하도록 하였다.
코드
|
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
|
import java.util.*;
public class Main {
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
static boolean[][] visited;
static int[][] board;
static int n, m;
static int cheese;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
board = new int[n][m];
cheese = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
board[i][j] = scan.nextInt();
if(board[i][j] == 1) cheese++;
}
}
int cheeseCount = 0;
int time = 0;
while(cheese != 0) {
cheeseCount = cheese;
time++;
visited = new boolean[n][m];
bfs();
}
System.out.println(time);
System.out.println(cheeseCount);
}
public static void bfs() {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[] {0, 0});
visited[0][0] = true;
while(!q.isEmpty()) {
int[] current = q.poll();
for(int i = 0; i < 4; i++) {
int nx = current[0] + dx[i];
int ny = current[1] + dy[i];
if(nx >= 0 && ny >= 0 && nx < n && ny < m && visited[nx][ny] == false) {
visited[nx][ny] = true;
if(board[nx][ny] == 0) {
q.offer(new int[] {nx, ny});
} else {
cheese--;
board[nx][ny] = 0;
}
}
}
}
}
}
|
cs |