2638번: 치즈
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표
www.acmicpc.net
0. 내부 공기엔 인접해도 녹지 않으므로, 외곽 공기에 대해서만 bfs를 진행.
- 0,0은 항상 밖의 공기이다
1. 0,0을 시작점으로, 외곽 공기를 bfs로 순회한다
- 치즈를 처음 만나면, 표시만 한다
- 치즈를 2번째로 만나면, 제거 대상 치즈로 판단, 저장한다
2. 1번에서 저장된 제거대상 치즈를 제거한다
3. 위 과정을 치즈가 없어질때까지 반복한다
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main{
static int[] dx= {1,0,-1,0};
static int[] dy= {0,1,0,-1};
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = pint(st.nextToken());
int m = pint(st.nextToken());
int[][]map = new int[n][m];
int chCnt=0;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine()," ");
for (int j = 0; j < m; j++) {
map[i][j]=pint(st.nextToken());
if(map[i][j]==1)chCnt++;
}
}
int time=0;
Queue<int[]>qu = new LinkedList<int[]>();
Queue<int[]>removeCh = new LinkedList<int[]>();
while(chCnt!=0) {
time++;
//bfs돌며 제거할 치즈 탐색
int[][]isV = new int[n][m];
qu.offer(new int[] {0,0});
isV[0][0]=1;
while(!qu.isEmpty()) {
int[] ch = qu.poll();
for (int i = 0; i < 4; i++) {
int tx = ch[0]+dx[i], ty=ch[1]+dy[i];
if(tx<0||tx>=n||ty<0||ty>=m)continue;
//미방문 공기
if(isV[tx][ty]==0 && map[tx][ty]==0) {
isV[tx][ty]=1;
qu.offer(new int[] {tx,ty});
}
//치즈 처음 만남
else if(isV[tx][ty]==0) {
isV[tx][ty]=1;
}
//치즈 2번째 만남
else if(isV[tx][ty]==1 && map[tx][ty]==1) {
isV[tx][ty]=2;
removeCh.offer(new int[] {tx,ty});
}
}
}
//녹을 치즈 제거
chCnt-=removeCh.size();
while(!removeCh.isEmpty()) {
int[] ch = removeCh.poll();
map[ch[0]][ch[1]]=0;
}
}
System.out.println(time);
}
static int pint(String s) {
return Integer.parseInt(s);
}
}
