반응형
알고리즘 분류 : DFS, BFS
1년마다 빙산이 녹는데, 빙산이 두 덩어리 이상으로 나눠지는 최초 연도를 구하는 문제다. 0은 바다고, 1 이상의 숫자는 빙산의 높이다. 빙산은 인접한 바다의 수(상하좌우)만큼 녹는다. 예를 들어 빙산의 위쪽과 왼쪽이 바다라면, 1년에 2만큼 녹는다.
- 입력받을 때 바다를 0대신 -1로 저장하고, 빙산의 위치는 Queue에 집어넣는다.
- 빙산이 녹는 것은 BFS와 비슷한 방법으로, 빙산에 인접한 상하좌우를 확인한다.
- 만약 인접한 곳이 바다라면, 인접한 수만큼 빙산을 녹인다.
- 빙산의 개수만큼 모두 녹이고, 연도를 1년 증가시킨다.
- DFS(또는 BFS)를 통해 두 덩어리 이상으로 쪼개져있는지 확인한다. 2개 이상이라면 연도를 반환하고 종료한다.
- 두 덩어리 이상이 될 때까지 계속 빙산을 녹이고, 빙산이 모두 녹을 때까지 두 덩어리가 안되면 0을 반환하고 종료한다.
C++ 소스코드
#include <cstdio> #include <cstring> #include <queue> using namespace std; struct ice { int x, y; }; int n, m; int a[301][301]; bool check[301][301]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; queue<ice> q; void dfs(int x, int y) { check[x][y] = true; for (int i=0; i<4; i++) { int nx = x+dx[i], ny = y+dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (check[nx][ny] || a[nx][ny] < 0) continue; dfs(nx, ny); } } bool counting() { int cnt = 0; memset(check, false, sizeof(check)); for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { if (!check[i][j] && a[i][j] > 0) { dfs(i, j); cnt++; if (cnt >= 2) return true; } } } return false; } void melting() { queue<ice> p; int len = q.size(); for (int i=0; i<len; i++) { int x = q.front().x, y = q.front().y; q.pop(); for (int k=0; k<4; k++) { int nx = x+dx[k], ny = y+dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (a[x][y] > 0 && a[nx][ny] == -1) a[x][y] -= 1; } if (a[x][y] > 0) q.push({x, y}); else if (a[x][y] == 0) p.push({x, y}); } while (!p.empty()) { int x = p.front().x, y = p.front().y; p.pop(); a[x][y] = -1; } } int solve() { int year = 0; while (!q.empty()) { melting(); year++; if (counting()) return year; } return 0; } int main() { scanf("%d %d", &n, &m); for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { scanf("%d", &a[i][j]); if (a[i][j]) q.push({i, j}); else a[i][j] = -1; } } printf("%d\n", solve()); return 0; }
PyPy3 소스코드
from collections import deque from sys import stdin input = stdin.readline n, m = map(int, input().split()) a = [list(map(int, input().split())) for _ in range(n)] q = deque() dx = (-1, 0, 1, 0) dy = (0, 1, 0, -1) for i in range(n): for j in range(m): if a[i][j] > 0: q.append((i, j)) else: a[i][j] = -1 def bfs(i, j, check): bq = deque() bq.append((i, j)) check[i][j] = True while bq: x, y = bq.popleft() for k in range(4): nx, ny = x+dx[k], y+dy[k] if nx < 0 or nx >= n or ny < 0 or ny >= m: continue if check[nx][ny] is False and a[nx][ny] > 0: bq.append((nx, ny)) check[nx][ny] = True def counting(): cnt = 0 check = [[False]*m for _ in range(n)] for _ in range(len(q)): x, y = q.popleft() q.append((x, y)) if check[x][y] is False: bfs(x, y, check) cnt += 1 if cnt >= 2: return True return False def melting(): p = deque() for _ in range(len(q)): x, y = q.popleft() for k in range(4): nx, ny = x+dx[k], y+dy[k] if nx < 0 or nx >= n or ny < 0 or ny >= m: continue if a[x][y] > 0 and a[nx][ny] == -1: a[x][y] -= 1 if a[x][y] > 0: q.append((x, y)) elif a[x][y] == 0: p.append((x, y)) while p: x, y = p.popleft() a[x][y] = -1 def solve(): year = 0 while q: melting() year += 1 if counting() is True: return year return 0 print(solve())
✓ Python 3로 제출하면 시간 초과가 나오므로, PyPy3로 제출해야 한다.
✓ C++과 달리 counting 함수 구현 방식을 약간 수정했다. DFS대신 BFS를 사용했고, N*M for문 대신 Queue를 사용했다.
참고
- 백준 온라인 저지 : BOJ 2573
반응형