난이도: 골드 IV
문제 링크: https://www.acmicpc.net/problem/2573
2573번: 빙산
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을
www.acmicpc.net
이번 문제부터 문제화면 캡쳐는 생략하겠습니다.
오늘도 풀 만한 문제가 없나~ 하고 보다가 고른 탐색 겸 구현 문제입니다.
구현 문제라서 코드의 길이가 길어지고 잔실수를 조심해야 하지만...
제가 접근한 방법입니다.
시작에 앞서, 빙산이 두 개 이상인지 판별하는 함수, 빙산을 1년어치만큼 녹이는 함수를 작성합니다. 빙산이 두 개 이상인지 판별하는 함수의 경우, 빙산이 없는 경우는 따로 체크합니다.
입력을 받고, while문을 이용하여 다음을 반복합니다.
- 빙산이 2개 이상인 경우, 종료합니다.
- 그렇지 않은 경우, 빙산을 1년치 녹입니다.
반복문이 종료된 후, 빙산이 없는 경우가 존재했다면 빙산이 다 녹을 때까지 2개 이상으로 나누어지지 않았다는 뜻이 됩니다. 이 경우 0을 출력하고 종료합니다. 이외의 경우, 빙산이 나뉘기까지 걸린 시간 (년)을 출력합니다.
빙산이 두 개 이상인지 판단하는 함수는 다음과 같이 구현했습니다.
빙산이 하나 존재할 때마다 개수를 셉니다. 한 덩어리 빙산은 BFS를 통해 체크하는데, BFS가 실행된 횟수가 곧 빙산의 수가 됩니다.
빙산을 1년치만큼 녹이는 경우는 다음과 같습니다.
주어진 영역 (n, m)과 같은 크기의 배열을 만들고, 값을 0으로 초기화합니다. 모든 빙산에 대해, 상하좌우 중 바다의 수만큼을 배열에 기록합니다. 이후, 배열에 기록된 수만큼 빙산의 값을 내립니다. 이 때, 빙산의 값이 음수가 되는 경우에는 0으로 고정합니다.
#include <iostream> | |
#include <queue> | |
using namespace std; | |
#define MAX_N 301 | |
bool cannot_divide = false; | |
int area[MAX_N][MAX_N]; | |
int candidate[MAX_N][MAX_N]; | |
int n, m; | |
int dx[4] = { -1, 0, 1, 0 }; | |
int dy[4] = { 0, 1, 0, -1 }; | |
queue<pair<int, int> > q; | |
int year_count = 0; | |
void area_input() { | |
for (int i = 0; i < n; i++) { | |
for (int j = 0; j < m; j++) { | |
cin >> area[i][j]; | |
} | |
} | |
return; | |
} | |
bool in_boundary(int x, int y) { | |
if (x >= 0 && x < n && y >= 0 && y < m) return true; | |
else return false; | |
} | |
void melt() { | |
for (int i = 0; i < n; i++) { | |
for (int j = 0; j < m; j++) { | |
candidate[i][j] = 0; | |
for (int dir = 0; dir < 4; dir++) { | |
int ni = i + dx[dir]; | |
int nj = j + dy[dir]; | |
if (!in_boundary(ni, nj)) continue; | |
if (area[ni][nj] == 0) candidate[i][j] += 1; | |
} | |
} | |
} | |
for (int i = 0; i < n; i++) { | |
for (int j = 0; j < m; j++) { | |
if (area[i][j] < candidate[i][j]) area[i][j] = 0; | |
else area[i][j] -= candidate[i][j]; | |
} | |
} | |
year_count++; | |
} | |
bool has_divided() { | |
int iceberg_count = 0; | |
//visited 초기화 | |
for (int i = 0; i < n; i++) { | |
for (int j = 0; j < m; j++) { | |
candidate[i][j] = 0; | |
} | |
} | |
for (int i = 0; i < n; i++) { | |
for (int j = 0; j < m; j++) { | |
if (area[i][j] != 0 && candidate[i][j] == 0) { | |
candidate[i][j] = 1; | |
while (!q.empty()) q.pop(); | |
q.push({ i, j }); | |
while (!q.empty()) { | |
int cx = q.front().first; | |
int cy = q.front().second; | |
q.pop(); | |
for (int dir = 0; dir < 4; dir++) { | |
int nx = cx + dx[dir]; | |
int ny = cy + dy[dir]; | |
if (!in_boundary(nx, ny)) continue; | |
if (area[nx][ny] == 0) continue; | |
if (candidate[nx][ny] == 1) continue; | |
candidate[nx][ny] = 1; | |
q.push({ nx, ny }); | |
} | |
} | |
iceberg_count++; | |
} | |
} | |
} | |
if (iceberg_count == 1) return false; | |
else if (iceberg_count == 0) { | |
cannot_divide = true; | |
return true; | |
} | |
else if (iceberg_count >= 2) return true; | |
} | |
int main() { | |
ios::sync_with_stdio(false); | |
cin >> n >> m; | |
area_input(); | |
while (1) { | |
if (has_divided()) break; | |
melt(); | |
} | |
if (cannot_divide) cout << 0; | |
else cout << year_count; | |
return 0; | |
} |
import java.util.*; | |
public class Main { | |
public static class Node { | |
private int x; | |
private int y; | |
public Node(int x, int y) { | |
this.x = x; | |
this.y = y; | |
} | |
public int getX() { | |
return this.x; | |
} | |
public int getY() { | |
return this.y; | |
} | |
} | |
public static int MAX_N = 301; | |
public static Boolean cannot_divide = false; | |
public static int area[][] = new int[MAX_N][MAX_N]; | |
public static int candidate[][] = new int[MAX_N][MAX_N]; | |
public static int n, m; | |
public static int dx[] = {-1, 0, 1, 0}; | |
public static int dy[] = {0, 1, 0, -1}; | |
public static Queue<Node> q = new LinkedList<>(); | |
public static int year_count = 0; | |
public static Boolean in_boundary(int x, int y) { | |
if (x >= 0 && x < n && y >= 0 && y < m) return true; | |
else return false; | |
} | |
public static void melt() { | |
for (int i = 0; i < n; i++) { | |
for (int j = 0; j < m; j++) { | |
candidate[i][j] = 0; | |
for (int dir = 0; dir < 4; dir++) { | |
int ni = i + dx[dir]; | |
int nj = j + dy[dir]; | |
if (!in_boundary(ni, nj)) continue; | |
if (area[ni][nj] == 0) candidate[i][j] += 1; | |
} | |
} | |
} | |
for (int i = 0; i < n; i++) { | |
for (int j = 0; j < m; j++) { | |
if (area[i][j] < candidate[i][j]) area[i][j] = 0; | |
else area[i][j] -= candidate[i][j]; | |
} | |
} | |
year_count++; | |
} | |
public static Boolean has_divided() { | |
int iceberg_count = 0; | |
for (int i = 0; i < n; i++) { | |
for (int j = 0; j < m; j++) { | |
candidate[i][j] = 0; | |
} | |
} | |
for (int i = 0; i < n; i++) { | |
for (int j = 0; j < m; j++) { | |
if (area[i][j] != 0 && candidate[i][j] == 0) { | |
candidate[i][j] = 1; | |
while(!q.isEmpty()) q.remove(); | |
q.add(new Node(i, j)); | |
while(!q.isEmpty()) { | |
Node node = q.poll(); | |
int cx = node.getX(); | |
int cy = node.getY(); | |
for (int dir = 0; dir < 4; dir++) { | |
int nx = cx + dx[dir]; | |
int ny = cy + dy[dir]; | |
if (!in_boundary(nx, ny)) continue; | |
if (area[nx][ny] == 0) continue; | |
if (candidate[nx][ny] == 1) continue; | |
candidate[nx][ny] = 1; | |
q.add(new Node(nx, ny)); | |
} | |
} | |
iceberg_count++; | |
} | |
} | |
} | |
if (iceberg_count == 1) return false; | |
else if (iceberg_count == 0) { | |
cannot_divide = true; | |
return true; | |
} | |
else return true; | |
} | |
public static void main(String[] args) { | |
Scanner sc = new Scanner(System.in); | |
n = sc.nextInt(); | |
m = sc.nextInt(); | |
sc.nextLine(); | |
for (int i = 0; i < n; i++) { | |
for (int j = 0; j < m; j++) { | |
int temp = sc.nextInt(); | |
area[i][j] = temp; | |
} | |
} | |
sc.nextLine(); | |
while(true) { | |
if(has_divided()) break; | |
melt(); | |
} | |
if (cannot_divide) System.out.println(0); | |
else System.out.println(year_count); | |
} | |
} |
기본적인 구현 부분에서 살짝 애를 먹고, Java로 코딩하면서 한번 더 헤맸습니다.
구현의 경우 1. 맨 처음부터 빙산이 두 개 이상으로 나뉜 경우, 2. 빙산이 끝까지 나뉘지 않는 경우 를 고려하지 못했습니다.
Java로 옮기며, C++처럼 별도의 area_input() 함수를 두지 않고 구현을 했는데, 이대로 하는 경우 NoSuchElement 에려가 떠서 하는 수 없이 입력을 main 함수로 옮겼습니다.

앞서 언급한 이유 때문에 시도 횟수가 좀 많았습니다 ㅎㅎ;
구현 문제는 잔실수가 없어야 해서 늘 고민이네요.
'알고리즘, 문제해결 > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 4179번] 불! (0) | 2022.01.23 |
---|---|
[백준 2606번] 바이러스 (0) | 2022.01.22 |
[백준 1697번] 숨바꼭질 (0) | 2021.12.31 |
[백준 10258번] 스위치 배열 (0) | 2021.11.01 |
[백준 1935번] 후위 표기식2 (0) | 2021.10.31 |
댓글