https://www.acmicpc.net/problem/2573
골드4 난이도, 정답률 26% 문제입니다.
문제 자체는 쉬우나, 문제를 해결하기 위해서 해야 하는게 많아서 정답률이 낮아보입니다.
이 문제는 두 가지의 문제를 복합시킨 느낌입니다.
풀이 후 밑에 어떤 문제인지 적어두겠습니다!
문제 분석
이 문제 자체는 어떻게 풀지 이해하기 쉬운 문제입니다.
주어진 설명 그대로 0으로 채워진 칸은 바닷물이므로, 1초가 지나면 이 바닷물과 닿은 빙산은 1칸씩 줄어들게 됩니다.
만약에 빙산 주변에 바닷물(0)이 2칸 있다면 1초 후에 빙산의 높이는 {now - 2} 가 됩니다.
모든 빙산에 대해서 빙산이 2개로 쪼개지는 순간의 시간을 출력해주면 정답이 됩니다.
백준 예시에 있는 그림입니다.
그림2에서 1초가 지나면 그림 3처럼 되는데, 그림2에서는 연결된 빙산이 1개지만 / 그림3에서는 빙산이 3조각으로 분리가 됐습니다.
이렇게 1개에서 1개 이상이 됐을 때 정답을 출력해주면 됩니다.
문제 풀이
이제 문제를 분석 했으니 풀어보도록 하겠습니다.
이런 문제를 보고 바로 DFS, BFS 같은 완전탐색을 떠올릴 수 있어야합니다.
그렇게 생각한 근거는 그래프를 쭉 순회하면서 빙산의 조각도 세어야하고, 빙산도 녹여야하기 때문입니다.
이 때 적절한 알고리즘은 BFS 혹은 DFS라고 볼 수 있습니다.
문제를 풀 때 또 좋은 방법을 말씀드리자면 문제를 먼저 컴퓨터가 아닌 사람의 논리로 풀어보고 순서를 정해주고 그 순서에 맞게 코딩을 하면 됩니다.
저는 이 문제를 다음과 같이 풀어야겠다고 생각했습니다.
- 데이터 입력 초기화
- loop start
- if(빙산 0개 혹은 분리 시 return)
- 빙산의 조각 세기
- 빙산 녹이기
- 정답 출력
이 순서로 풀었고 2번 부분을 가장 신경 써서 풀었습니다.
빙산을 녹이기 전에 빙산의 조각 수를 먼저 세어 주었습니다.
이 부분은 dfs로 해결했습니다.
빙산을 녹이는 부분도 dfs로 해결할 수 있지만, 이번에는 bfs로 풀어봤습니다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
private static final Scanner sc = new Scanner(System.in);
private static int n, m;
private static int[][] map;
private static boolean[][] visited;
private static int[][] pos = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
private static int answer = 0;
public static void main(String[] args) {
// 1. 데이터 셋업
initData();
// 2. loop (빙산 세기, 빙산 녹이기)
startLoop();
// 3. 데이터 출력
printAnswer();
}
private static void initData() {
n = sc.nextInt();
m = sc.nextInt();
map = new int[n][m];
visited = new boolean[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
map[i][j] = sc.nextInt();
}
}
}
private static void startLoop() {
while (true) {
// 1. 빙산의 조각 세기 (if. 빙산 0개, 혹은 분리시 return)
int ice = countIce();
if (ice == 0) {
answer = 0;
return;
}
if (ice >= 2) {
return;
}
// 2. 빙산 녹이기
bfsOfMeltingIce();
answer++;
}
}
private static int countIce() {
visited = new boolean[n][m];
int ice = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && map[i][j] > 0) {
dfsOfCountIce(i, j);
ice++;
}
}
}
return ice;
}
private static void dfsOfCountIce(int row, int col) {
visited[row][col] = true;
for (int i = 0; i < pos.length; i++) {
int nr = row + pos[i][0];
int nc = col + pos[i][1];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && map[nr][nc] != 0 && !visited[nr][nc]) {
dfsOfCountIce(nr, nc);
}
}
}
private static void bfsOfMeltingIce() {
visited = new boolean[n][m];
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] > 0) {
queue.add(new int[]{i, j});
visited[i][j] = true;
}
}
}
while (!queue.isEmpty()) {
int[] info = queue.poll();
int blank = 0;
for (int i = 0; i < pos.length; i++) {
int nr = info[0] + pos[i][0];
int nc = info[1] + pos[i][1];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && !visited[nr][nc] && map[nr][nc] == 0) {
blank++;
}
}
if (map[info[0]][info[1]] - blank < 0) {
map[info[0]][info[1]] = 0;
} else {
map[info[0]][info[1]] -= blank;
}
}
}
private static void printAnswer() {
System.out.println(answer);
}
}
비슷한 문제
이 문제는 두 가지의 문제가 섞인 것 같다고 위에서 언급했습니다.
먼저 위 문제에서 빙산을 세는 부분은 [백준 2667 : 단지번호붙이기] 문제와 유사합니다.
https://www.acmicpc.net/problem/2667
또한 위 문제에서 빙산을 녹이는 부분은 [백준 2636 : 치즈] 문제와 유사합니다.
https://www.acmicpc.net/problem/2636
'PS' 카테고리의 다른 글
[자바] 백준 N과 M 시리즈(1~4) / 백트래킹 (0) | 2023.01.26 |
---|---|
[자바] 백준 17609 : 회문 (문자열) (1) | 2023.01.19 |
[자바] 백준 13023 : ABCDE / 그래프, DFS 풀이 (1) | 2023.01.16 |
[자바] 프로그래머스 - 개인정보 수집 유효기간 (2023 카카오 블라인드) 풀이 (0) | 2023.01.08 |
[자바] 백준 1328 : 고층 빌딩 (DP 풀이) 접근 방법 및 풀이 (1) | 2022.12.27 |