🔒[문제 url]
https://www.acmicpc.net/problem/2573
🔑알고리즘
빙산을 녹이는 과정만 구현을 해낸다면, 이후는 DFS or BFS로 얼음덩이의 수만 세어주면 됐던 문제.
1. 얼음덩이의 개수를 세어본다.
2. 얼음덩이의 개수가 한 개일 경우, 이중for문으로 탐색하며 빙산을 녹인다.
3. 얼음덩이가 두 개 이상 혹은 사라질 때까지 위 과정을 반복한다.
- 빙산을 녹일때 주의해야할 점
- 이중for문으로 한 지점을 방문할때마다 녹인다면, 현재의 지점이 이전에 녹아내린 지점의 영향을 받게되므로 오류가 발생한다.
- 따라서, 방문할때마다 녹이는 것이 아닌 모든 지점에 대해 녹아내릴 양을 기억해둔 후, 이중for문 탐색 직후에 녹아내리도록 처리한다.
- 출력시 주의해야할 점
- 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면, 년수를 출력하는 것이 아닌 0을 출력
🐾부분 코드
int icebergCount()
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (!visited[i][j] && map[i][j] > 0)
{
if (!count) // 아직 빙산을 못 발견했다면
{
BFS({ i,j });
count++;
}
else return 2; // 빙산이 1개를 넘으면 2 return(어차피 2이상이면 진행 종료)
}
}
return count; // 빙산이 없으면 0으로 return
}<빙산 덩어리 개수 반환 함수>
얼음이 있는 지점을 발견하면, BFS를 통해 해당 지점이 속한 덩어리에 방문 처리를 한다. 얼음 덩어리가 두 개 이상이면 어차피 녹이는 작업은 진행하지 않으므로, count가 0일때에만 BFS탐색을 진행한다.
얼음이 있는 지점이 없다면 0을 반환한다.
void BFS(pii pos)
{
queue<pii> q;
q.push(pos);
while (!q.empty())
{
pii now = q.front();
q.pop();
visited[now.first][now.second] = true;
for (int i = 0; i < 4; i++)
{
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int nx = now.first + dx[i], ny = now.second + dy[i];
pii np = { nx,ny };
if (!visited[np.first][np.second] && map[np.first][np.second])
{
q.push(np);
visited[np.first][np.second] = true;
}
}
}
}<BFS 함수>
얼음이 발견된 지점을 시작으로 해당 지점이 속한 덩어리의 모든 지점에 대하여 방문 처리를 한다. DFS 함수로 진행해도 무방하다.
pii는typedef pair<int, int> pii;로 간결화한 코드이다.
void melt()
{
struct meltInfo
{// 녹아내릴 위치와 양 저장 구조체
int x;
int y;
int count;
};
vector<meltInfo> meltCnt; // 녹을 정보를 push해둠
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (map[i][j] > 0)
{
int cnt = 0; // 녹을 양
for (int k = 0; k < 4; k++)
{// 동서남북 탐색
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int nx = i + dx[k], ny = j + dy[k];
if (map[nx][ny] == 0)
{// 동서남북 중 바닷물이 접해있으면
cnt++;
}
}
meltInfo mI;
mI.x = i; mI.y = j; mI.count = cnt;
meltCnt.push_back(mI);
}
}
// vector 순회하며 녹이기
for (int i = 0; i < meltCnt.size(); i++)
{
map[meltCnt[i].x][meltCnt[i].y] -= meltCnt[i].count;
if (map[meltCnt[i].x][meltCnt[i].y] < 0) map[meltCnt[i].x][meltCnt[i].y] = 0;
}
}<빙산 녹이는 함수>
meltInfo라는 구조체를 생성해주었다. 위에서 설명했듯 for문 탐색중 녹이는 작업을 진행하면 이후 지점들이 영향을 받으므로, 빙산의 각 지점에 대한 위치와 녹아내릴 양을 vector에 저장해둔 후,meltInfo mI; mI.x = i; mI.y = j; mI.count = cnt; meltCnt.push_back(mI);meltInfo를 담아둔 vector를 순회하며 녹이는 과정을 진행한다.
void SOLVE()
{
int ibC, previbC = 0;
while (true)
{
memset(visited, false, sizeof(visited));
ibC = icebergCount(); // 현재 덩어리 수
if (previbC == 1 && ibC == 0) ans = 0; // 전부 녹을때까지 한 덩어리라면 0 출력
previbC = ibC; // 이전 덩어리 수
if (ibC != 1) break;
ans++;
melt();
}
cout << ans;
}<1, 2번 과정 반복 함수>
ibC(현재 얼음 덩어리의 수)와 previbC(이전 얼음 덩어리의 수)를 선언해준 뒤, 위에서 언급한 출력시 주의해야할 점에 대한 예외 처리를 해준다.
전부 녹을때까지 한 덩어리였다는 것은, previbC == 1 and ibC == 0.
이 경우를 제외하고는, 얼음 덩어리가 1이 아닌 경우 과정을 종료하고 년수를 출력한다.memset(visited, false, sizeof(visited));위 코드를 통해 BFS탐색전 방문 정보를 초기화 해주는 것을 잊지말자.
🪄전체 코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stdio.h>
#include <ctime>
#include <memory.h> // memset
#include <numeric>
#include <stack>
#include <sstream>
using namespace std;
typedef pair<int, int> pii;
int n, m;
int map[300][300];
bool visited[300][300];
int ans = 0;
void INPUT()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> map[i][j];
}
void BFS(pii pos)
{
queue<pii> q;
q.push(pos);
while (!q.empty())
{
pii now = q.front();
q.pop();
visited[now.first][now.second] = true;
for (int i = 0; i < 4; i++)
{
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int nx = now.first + dx[i], ny = now.second + dy[i];
pii np = { nx,ny };
if (!visited[np.first][np.second] && map[np.first][np.second])
{
q.push(np);
visited[np.first][np.second] = true;
}
}
}
}
int icebergCount()
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (!visited[i][j] && map[i][j] > 0)
{
if (!count) // 아직 빙산을 못 발견했다면
{
BFS({ i,j });
count++;
}
else return 2; // 빙산이 1개를 넘으면 2 return(어차피 2이상이면 진행 종료)
}
}
return count; // 빙산이 없으면 0으로 return
}
void melt()
{
struct meltInfo
{
int x;
int y;
int count;
};
vector<meltInfo> meltCnt; // 녹을 빙산의 위치와 녹을 양을 push해둠
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (map[i][j] > 0)
{
int cnt = 0; // 녹을 양
for (int k = 0; k < 4; k++)
{// 동서남북 탐색
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int nx = i + dx[k], ny = j + dy[k];
if (map[nx][ny] == 0)
{// 동서남북 중 바닷물이 접해있으면
cnt++;
}
}
meltInfo mI;
mI.x = i; mI.y = j; mI.count = cnt;
meltCnt.push_back(mI);
}
}
// vector 순회하며 녹이기
for (int i = 0; i < meltCnt.size(); i++)
{
map[meltCnt[i].x][meltCnt[i].y] -= meltCnt[i].count;
if (map[meltCnt[i].x][meltCnt[i].y] < 0) map[meltCnt[i].x][meltCnt[i].y] = 0;
}
}
void SOLVE()
{
int ibC, previbC = 0;
while (true)
{
memset(visited, false, sizeof(visited));
ibC = icebergCount();
if (previbC == 1 && ibC == 0) ans = 0; // 전부 녹을때까지 한 덩어리라면 0 출력
previbC = ibC;
if (ibC != 1) break;
ans++;
melt();
}
cout << ans;
}
int main()
{
INPUT();
SOLVE();
}🥇문제 후기
문제 풀이보다 포스팅이 더 오래 걸린 문제.. 0을 출력하는 경우를 놓쳐 한번 틀렸으나, 다행히 해당 케이스를 포함해 다른 모든 경우의 수를 금방 캐치해서 금방 풀었다. 다만, 'BFS탐색과 melt를 분리하지 않고 하나의 이중for문으로 문제를 풀 수는 없을까?' 라는 고민을 해보려했으나..
귀찮다. 얼른 집 가야지. 코드도 더 간결하게 쓸 수 있긴한데..
💕오류 지적 및 피드백은 언제든 환영입니다. 복제시 출처 남겨주세요!💕
I AM WHO I AM