[백준] 2638번:치즈 (Java 자바)

[백준] 2638번:치즈 (Java 자바)

반응형

문제

https://www.acmicpc.net/problem/2638

풀이 및 소스코드

간단한 DFS/BFS 문제인 줄 알았으나,

바깥공기와 내부공기(?) 를 나눠야 하는 것에서 조금 멈칫했다.

문제를 보면

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다.

라는 문장이 있다. !

모눈종이의 맨 가장자리는 치즈가 놓이지 않는 즉, 바깥 공기가 존재하는 곳이다.

따라서 녹을 치즈를 찾기 전, 모눈종이의 맨 가장자리와 연결되어 있는 곳들의 값들을 -1로 바꿔준다.

그렇게 되면,

-1 인 곳 : 바깥 공기가 존재하는 곳

0인 곳 : 안쪽 공기가 존재하는 곳

으로 나뉠 수 있다.

위의 설명을 그림으로!!

그 다음부터는

값이 1인 곳들을 찾아 상하좌우 중 -1인 곳에 대해 카운트를 진행한다.

-1 인 곳이 주변에 두개 이상 존재한다면 (cnt>=2)

단, 치즈가 한 번 녹을 때 마다 바깥 공기 부분과 안쪽 공기 부분은 바뀔 수 있으므로 한 시간이 지날 때 마다 이 과정을 반복해준다.

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int[][] map = new int[n][m]; for(int i=0;i q = new LinkedList<>(); q.add(new Integer[]{0,0}); map[0][0]=-1; while(!q.isEmpty()) { //바깥공기 영역 구하기 !! //bfs 사용 Integer[] tmp = q.poll(); int x = tmp[0]; int y = tmp[1]; for(int i=0;i<4;i++) { int nowx = x+dx[i]; int nowy = y+dy[i]; if(nowx<0||nowy<0||nowx>=n||nowy>=m) { continue; } if(map[nowx][nowy]==0) { map[nowx][nowy]=-1; q.add(new Integer[] {nowx,nowy}); } } } Queue xx = new LinkedList<>(); Queue yy = new LinkedList<>(); for(int i=0;i=n||nowy>=m) { continue; } //범위 나가버리면 컨티뉴 if(map[nowx][nowy]==-1) { cnt ++; if(cnt>=2) break; //두개이상이 비었다면 더이상 볼 필요 없으니 break } } if(cnt>=2) { xx.add(i); yy.add(j); //없어질 치즈 좌표를 넣어준다. } } } } if(xx.isEmpty()) { System.out.println(res); System.exit(0); } //사라질 치즈 후보가 없다는 것은 치즈가 모두 녹아서 없어졌다는 것. //res를 출력해주고 종료해주자. //종료가 되지 않았다는 것은 아직 치즈가 있다는 것. //없어질 치즈들을 없애주고, while문 진행 res++; while(!xx.isEmpty()) { map[xx.poll()][yy.poll()] = 0; } for(int i = 0;i

반응형

from http://jainn.tistory.com/261 by ccl(A) rewrite - 2021-09-14 00:26:52