[백준] 2573번 빙산

www.acmicpc.net/problem/2573

2573번: 빙산

BFS기반으로 알고리즘을 구성했다. 

코드 완성해놓고 47번째줄에 board[cur.first][cur.second]를 board[i][j]라 써놓고 계속 디버깅하고있었다;;

처음 코드를 작성할 때 신경을 많이 써서 작성해야겠다.

 

변수

board - 빙산의 높이가 저장되는 배열

vis - 매년 빙산이 영향 받았는지 여부를 0, 1로 표현

q - 빙산의 좌표를 입력 (x, y)

year - 매 시행이 몇 년째의 시행인지를 의미

cnt - 매년 빙산의 덩어리 수

 

알고리즘 방식

먼저 생각을 해야되는 부분이 BFS를 통해 cnt(빙산 덩어리 수)를 찾는 과정이 0년 때라면,

                                      BFS과정 중 빙산의 높이 변화는 1년 때를 만들어 가는 과정이다.

즉 첫 번째 BFS과정을 통해 배열 board에는 1년이 지난 후 빙산의 높이가 저장되어 있고,

               cnt에는 0년때의 빙산의 덩어리 수가 기록되어있다.

 

1. BFS를 진행하기에 앞서 year과 cnt를 통해 위의 방식을 구현해놓아야한다.

1-1. cnt를 통해 while문을 실행하는데 매년 cnt = 0으로 초기화 해주어야 하고 while문 실행 결과

      cnt == 0이면 빙산이 없는 것이기 때문에 while(cnt != 0)으로 조건문 생성

1-2 year = 0으로 초기화 후, 앞선 while문 과정 끝에

                                     cnt >= 2이면 원하는 결과 값을 도출할 수 있으므로 return year

                                     cnt >= 2이 아니면 다음해로 넘어가므로 year++

2. BFS를 기반으로 cur에 대해 주변 4방향을 탐색하여 0이면서 vis == 0일 경우

   cur가 가르키는 board의 값을 1씩 감소시킨다. 

2-1. 위와 같은 방식을 통해 0이된 빙산은 vis == 1이므로, 후에 다른 빙산에 영향을 주지 않는다.

 

후기

알고리즘을 생각해내는 것보다 변수들의 적당한 위치를 찾아서 넣어주는 과정이 더 힘들었다. 

항상 큰 틀에서 알고리즘을 생각하고 코드를 짜는 습관을 들여야 될 것 같다. 

생각나는데로 적어나가다보면 디버깅할때 자꾸 헷갈린다 ㅠ.

 

 

#include <iostream>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int N, M;
int board[300][300];
int vis[300][300];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
queue<pair<int, int>> q;
 
int BFS() {
	int year = 0;
	int cnt = 1;
	while (cnt != 0) {
		cnt = 0;		
		fill(&vis[0][0], &vis[299][300], 0);
 
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
 
				if (board[i][j] != 0 && vis[i][j] == 0) {
					q.push({ i, j });
					vis[i][j] = 1;
					cnt++;
 
					while (!q.empty()) {
						pair<int, int> cur = q.front();
						q.pop();
 
						for (int dir = 0; dir < 4; dir++) {
							int nx = cur.first + dx[dir];
							int ny = cur.second + dy[dir];
 
							if (nx < 0 || ny < 0 || nx >= N || ny >= M)
								continue;
 
							if (board[nx][ny] != 0 && vis[nx][ny] == 0) {
								vis[nx][ny] = 1;
								q.push({ nx, ny });
							}
 
							if (board[nx][ny] == 0 && vis[nx][ny] == 0) {
								if (board[cur.first][cur.second] != 0)
									board[cur.first][cur.second]--;
							}
						}
					}
				}
			}
		}
		if (cnt >= 2) 
			return year;			
		
		year++;
	}	
	return 0;
}
 
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
 
	cin >> N >> M;
 
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> board[i][j];
 
	cout << BFS();
}