Life Engineering
[BOJ 2638] 치즈 (Java) 본문
https://www.acmicpc.net/problem/2638
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_BOJ_2638 {
static int N, M;
static int[][] map;
static boolean[][] isAir;
static int air;
static int answer=0;
static ArrayList<int[]> li=new ArrayList<>();
static int[] dr= {-1,1,0,0};
static int[] dc= {0,0,-1,1};
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
N=Integer.parseInt(st.nextToken());
M=Integer.parseInt(st.nextToken());
map=new int[N][M];
isAir=new boolean[N][M];
li.add(new int[] {0,0});
for (int i = 0; i < N; i++) {
st=new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j]=Integer.parseInt(st.nextToken());
}
}
while (true) {
check();
if (air==N*M) break;
li.clear();
melt();
answer++;
}
System.out.println(answer);
}
private static void check() { //외부 공기 표시하기
Queue<int[]> q=new LinkedList<>();
for (int[] arr : li) {
q.add(arr);
isAir[arr[0]][arr[1]]=true;
air++;
}
while (!q.isEmpty()) {
int[] pos=q.poll();
for (int i=0; i<4; i++) {
int nr=pos[0]+dr[i];
int nc=pos[1]+dc[i];
if (nr<0 || nc<0 || nr>=N || nc>=M) continue;
if (map[nr][nc]==0 && !isAir[nr][nc]) {
isAir[nr][nc]=true;
air++;
q.add(new int[] {nr,nc});
}
}
}
}
private static void melt() {
for (int i = 0; i < N; i++) {
for (int j=0; j<M; j++) {
if (map[i][j]==0) continue;
int cnt=0;
for (int d=0; d<4; d++) {
int nr=i+dr[d];
int nc=j+dc[d];
if (isAir[nr][nc]) cnt++;
}
if (cnt>=2) {
li.add(new int[] {i,j});
}
}
}
for (int[] arr : li) {
map[arr[0]][arr[1]]=0;
}
}
}
프로세스는 다음과 같다.
1. 외부 공기 갱신하기
2. 외부 공기가 N*M개(즉 치즈가 0개)면 해당 프로세스를 종료
3. 치즈 리스트 비운 후, 갱신된 외부 공기에 대해 녹을 치즈를 치즈 리스트에 넣은 후, 녹인다(map에 0 표시)
외부 공기 갱신은 check() 함수로,
이전에 녹은 치즈 (첫번째 호출 때는 (0,0)) 의 좌표들을 큐에 넣어주고, BFS 탐색을 진행하면서
map이 0이고 isAir가 false(즉 미방문)인 위치에 대해 모두 방문해준다.
melt() 함수에서는, map을 모두 돌면서 치즈인 위치에 대해, 주변 4방향을 모두 탐색하면서 그 중 외부 공기로 표시된 것이 2개 이상이면 녹을 치즈 리스트에 넣어준다.
다른분의 코드(https://yabmoons.tistory.com/342) 를 보니
녹일 치즈를 선정할 때 map의 원소를 모두 탐색하는 것이 아니라 입력받을 때 치즈의 위치를 리스트에 따로 저장한다.
그 치즈 리스트를 순회하면서 이미 녹인 치즈일 경우 제외하고, 아직 녹지 않은 치즈면 탐색을 진행해서 외부공기와 닿는 면이 얼마나 있는지 체크한다. 이 코드 역시, 녹인 치즈를 큐에 넣어서 외부 공기를 표시해 주었다.
'Problem Solving' 카테고리의 다른 글
[BOJ 16928] 뱀과 사다리 게임 (Java) (0) | 2022.03.20 |
---|---|
[BOJ 2565] 전깃줄 (Java) (0) | 2022.03.17 |
[프로그래머스] 이중 우선순위 큐 (Java) (0) | 2022.03.17 |
[프로그래머스] 기지국 설치 (Java) (0) | 2022.03.17 |
[BOJ 9935] 문자열 폭발 (Java) (0) | 2022.03.16 |