[백준 온라인 저지(BOJ)] 2636번 치즈 문제 자바(java) 풀이

BOJ 2636번 치즈 문제 자바(java) 풀이

• 랭크 : 골드5
• 백준 온라인 저지(BOJ) 2636번 치즈 문제 자바 풀이
• 백준 2636번 치즈

백준 2636번 치즈 코드

---

문제정리

1. 이 문제에서 주어진 정사각형 칸은 크게 세가지 영역으로 나뉨을 이해한다.

• 바깥쪽 공기 (치즈를 녹임)
• 치즈
• 안쪽 공기 (치즈를 녹일 수 없음)

2. 바깥 공기와 접촉된 치즈는 녹는다.
3. 녹아서 안쪽 공기도 바깥과 연결 된다면 그 공기에 의해서도 치즈가 녹을 수 있다.
4. 치즈가 모두 녹아 없어지는데 걸리는 시간과 모두 녹기 전 치즈의 수를 구한다

---

문제풀이

bfs나 dfs를 이용하여 문제를 풀 수 있습니다.
이 문제는 구역을 나누는게 핵심입니다.

1. dfs를 통해 치즈가 아니거나 바깥 공기인 경우 3으로 바꿔준다.
2. dfs2를 통해 바깥공기(3)와 닿아서 녹게 될 치즈를 2로 바꿔준다.
3. 녹게 될 치즈를 녹여서 공기로 바꿔준다. 2에서 바로 공기로 바꾸게 되면 연쇄적으로 치즈가 모두 녹아버리게 된다. 이때 치즈의 수도 같이 구한다.
4. 남아있는 치즈의 수가 0이 되기 전까지 반복한다.

---

dfs1 설명

이 함수를 이용해 바깥의 공기를 모두 탐색하며 찾아간다.
0. 4 방향을 가지고 탐색하며 찾아가는 dfs를 이용하였다.

1. 찾아갈 곳이 있다면 계속 찾아갈 수 있도록 while문을 돈다.
2. stack에서 하나를 뽑아서 그 위치에서 위, 아래, 왼쪽, 오른쪽을 탐색한다.
3. 탐색하면서 배열의 범위를 넘지 않는지 먼저 확인한다.
4. 그리고 visited를 이용하여 방문한 곳은 다시 방문하지 않도록 하여 redundancy를 줄인다.
5. 방문하지 않았고 0이나 공기(3)라면 공기로 바꾸고 stack에 넣어두고 다음에 탐색한다.

---

dfs2 설명

이를 이용하여 공기와 닿아서 놓을 치즈를 판별한다.

1. 이 함수도 dfs1 처럼 같은 방식으로 순회한다.
2. 현재 위치가 공기이면 일단 순회 하기 위해서 stack에 넣고 visited 처리를 한다.
   • 여기서 그 위치 주변에 치즈가 있다면 그 치즈는 녹게 되므로 PREAIR로 처리해준다.

---

예제1의 경우 진행과정

1. 바깥 공기를 판별한다.

   333333333333
   333333333333
   333333311333
   311133311333
   311111133333
   311111011333
   311110011333
   331100011333
   331111111333
   331111111333
   331111111333
   331111111333
   333333333333

2. 바깥 공기와 닿아서 녹을 치즈를 표시한다(2로 표시)

   333333333333
   333333333333
   333333322333
   322233322333
   321122233333
   321111022333
   321110012333
   332100012333
   332111112333
   332111112333
   332111112333
   332222222333
   333333333333

3. melting을 호출하여 치즈를 녹이고 다시 bfs를 호출하여 공기로 뒤덮은 모습이다.

   333333333333
   333333333333
   333333333333
   333333333333
   331133333333
   331111333333
   331113313333
   333133313333
   333111113333
   333111113333
   333111113333
   333333333333
   333333333333

333333333333
333333333333
333333333333
333333333333
332233333333
332122333333
332123323333
333233323333
333222223333
333211123333
333222223333
333333333333
333333333333

333333333333
333333333333
333333333333
333333333333
333333333333
333133333333
333133333333
333333333333
333333333333
333311133333
333333333333
333333333333
333333333333

333333333333
333333333333
333333333333
333333333333
333333333333
333233333333
333233333333
333333333333
333333333333
333322233333
333333333333
333333333333
333333333333