728x90
반응형
|
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
// 한 행을 쭉 갔을 때 4가지 방향 중 하나라도 벽이면 1시간뒤에 사라질 치즈임
public static int n;
public static int m;
public static int arr[][];
public static int dx[]={-1,1,0,0};
public static int dy[]={0,0,-1,1};
public static boolean visited[][];
public static List<Integer>ans=new ArrayList<>();
public static class Node{
int x;
int y;
public Node(int x,int y){
this.x=x;
this.y=y;
}
}
public static void BFS(){
//치즈 안에 있는 공기를 파악하기 bfs를 해서 벽을 포함하지 않으면 치즈 안에 있는 공기임
Queue<Node>queue=new LinkedList<>();
visited=new boolean[n][m];
int sum=0;
queue.add(new Node(0,0));
arr[0][0]=3;
while(!queue.isEmpty()){
Node node=queue.poll();
for(int k=0;k<4;k++){
int nx=node.x+dx[k];
int ny=node.y+dy[k];
if(0<=nx&&nx<n&&0<=ny&&ny<m){
if(arr[nx][ny]==0&&!visited[nx][ny]){
arr[nx][ny]=3;
queue.add(new Node(nx,ny));
}
}
}
}
// for(int i=0;i<n;i++){
// for(int j=0;j<m;j++){
// System.out.print(arr[i][j]+" ");
// }
// System.out.println();
// }
// 찐 공기의 상하좌우에 치즈가 있으면 걔도 3으로 만들기
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(arr[i][j]==3){
for(int k=0;k<4;k++){
int nx=i+dx[k];
int ny=j+dy[k];
if(0<=nx&&nx<n&&0<=ny&&ny<m){
if(arr[nx][ny]==1){
arr[nx][ny]=2;
}
}
}
}
}
}
// System.out.println("=======");
//
// for(int i=0;i<n;i++){
// for(int j=0;j<m;j++){
// System.out.print(arr[i][j]+" ");
// }
// System.out.println();
// }
sum=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(arr[i][j]==1){
sum++;
}
}
}
ans.add(sum);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(arr[i][j]==2||arr[i][j]==3){
arr[i][j]=0;
}
}
}
// System.out.println("=======");
//
// for(int i=0;i<n;i++){
// for(int j=0;j<m;j++){
// System.out.print(arr[i][j]+" ");
// }
// System.out.println();
// }
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new BufferedReader(new InputStreamReader(System.in)));
StringTokenizer st;
st=new StringTokenizer(br.readLine());
n=Integer.parseInt(st.nextToken());
m=Integer.parseInt(st.nextToken());
arr=new int[n+1][m+1];
for(int i=0;i<n;i++){
st=new StringTokenizer(br.readLine());
for(int j=0;j<m;j++){
arr[i][j]=Integer.parseInt(st.nextToken());
}
}
int first=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(arr[i][j]==1){
first++;
}
}
}
BFS();
while(true){
int size=ans.size();
if(ans.get(size-1)==0){
break;
}else{
BFS();
}
}
if(ans.size()==1){
System.out.println(1);
System.out.println(first);
}else{
System.out.println(ans.size());
System.out.println(ans.get(ans.size()-2));
}
}
}
|
cs |
정말 오랜만에 혼자 힘으로 풀었다.
이 문제는 치즈를 관점으로 두는게 아닌 공기를 관점으로 둬야 한다.
찐 공기와 치즈 사이에 있는 가짜 공기를 걸러내는 작업이 필요한데
찐 공기는 가장자리부터 시작해서 BFS를 돌리면 된다. 찐공기에는 3을 찍어줬다. 그러면 0인 애들이 남는데 얘네가 치즈 사이에 있는 가짜 공기들이다. 이제 찐공기의 상하좌우에 있는 치즈들에는 2를 찍어준다 (바로 3을 찍어주면 dfs돌리면서 문제가 생긴다. 한시간뒤에 공기가 되는데 이미 공기라고 인식해벌임...)
그러면 공기에 닿지 않은 치즈들은 1이고 얘네만 리스트에 담아주면 끝난당!
728x90
반응형
'알고리즘 > 그래프' 카테고리의 다른 글
| [java 백준]실버 2/ 2644번 촌수 계산 (0) | 2023.01.18 |
|---|---|
| [java 백준] 실버 1/ 2368번 안전영역 (0) | 2023.01.15 |
| [java 백준] 2887번 행성터널 (1) | 2022.10.01 |
| [java 백준] 10775번 공항 (0) | 2022.09.10 |
| [java 백준] 20040번 사이클게임 (0) | 2022.09.09 |
댓글