[백준] No.2573 - 빙산 (C++)

문제

https://www.acmicpc.net/problem/2573

2573번: 빙산

 

풀이

meltDfs( ) : 주위의 블록을 확인하여, 0이라면 높이를 1씩 녹이고, 아니라면 재귀로 접근

r, c로 ice배열의 위치를 받아 Dfs로 위,양옆,아래의 네 방향으로 Dfs접근한다.

접근할 ice[nr][nc]가 0이 아니라면(빙산이라면)  visited[nr][nc]로 해당 위치를 방문했는지 확인한다.

방문하지 않았다면 그대로 meltDfs를 재귀호출 한다.

접근할 ice[nr][nc]가 0이라면 바다라는 뜻인데, 만약 visited[nr][nc]가 true라면 해당 블록은 빙산이 모두 녹아 0이된 경우이다.(바다는 항상 visited=false) . visited[nr][nc]가 false이고 ice[r][c]가 0 이상이면 높이를 1 줄여준다.

 

Dfs( ) : 연결된 빙산을 모두 방문

 

Routine( ) : 반복문을 돌며 meltDfs( )를 호출하고 Dfs( )로 빙산이 두 덩어리가 되는 시점을 반환

passed_year를 반복문을 돌 때마다 1씩 증가

함수들을 호출하기 전에 memset으로 visited를 false로 초기화 해주자.

먼저 Dfs()를 호출해 연결된 빙산의 덩어리의 개수를 cnt에 기록

만약 cnt=0이라면, 빙산이 없는 것으로 0을 반환

cnt>1 이라면, 두 덩어리 이상이 됐으므로 passed_year를 반환

cnt가 아직 1이라면, meltDfs를 ice[i][j] 가 0이 아닌(빙산인) 위치에서 호출한다.

 

소스코드

 

	#include <iostream>
	#include<string.h>
	using namespace std;
	int n,m;
	int ice[300][300];
	//int copy[300][300];
	bool visited[300][300];
	int ch_r[4] = {1,0,-1,0};
	int ch_c[4] = {0,1,0,-1};
	void meltDfs(int r,int c){
	int nr,nc;
	visited[r][c] = true;
	for(int i=0; i<4 ; ++i){
	nr = r+ ch_r[i];
	nc = c+ ch_c[i];
	if(0<=nr && nr<n && 0<=nc && nc<m){
	if(ice[nr][nc] != 0){
	if(!visited[nr][nc]) //ret가 0으로 변화했을때를 대비해 이미 방문되면 영향x
	meltDfs(nr, nc);
	}else{
	if(!visited[nr][nc] && ice[r][c]>0) //ret가 0으로 변화했을때를 대비해 이미 방문되면 영향x , 0이되면 그대로 놔둠 ->핵심쓰
	--ice[r][c];
	}
	}
	}
	}
	void Dfs(int r,int c){
	int nr,nc;
	visited[r][c] = true;
	for(int i=0; i<4 ; ++i){
	nr= r+ ch_r[i];
	nc = c+ ch_c[i];
	if(0<=nr && nr<n && 0<=nc && nc<m){
	if(!visited[nr][nc] && ice[nr][nc] != 0)
	Dfs(nr, nc);
	}
	}
	}
	int Routine(){
	int passed_year=0;
	while(1){
	int cnt=0;
	memset(visited, false, sizeof(visited));
	for(int i=0; i<n ; ++i){
	for(int j=0; j<m ; ++j){
	if(!visited[i][j] && ice[i][j] != 0){
	Dfs(i, j);
	++cnt;
	}
	}
	}
	if(cnt==0)
	return 0;
	else if(cnt>1){
	return passed_year;
	}else{ //아직 1일때
	++passed_year;
	memset(visited, false, sizeof(visited));
	for(int i=0; i<n ; ++i){
	for(int j=0; j<m ; ++j){
	if(!visited[i][j] && ice[i][j] != 0){
	meltDfs(i, j);
	}
	}
	}
	}
	}
	}
	int main() {
	cin>>n>>m;
	for(int i=0; i<n ; ++i){
	for(int j=0; j<m ; ++j){
	cin>>ice[i][j];
	}
	}
	int result = Routine();
	cout<<result<<'\n';
	return 0;
	}

view raw 빙산.cpp hosted with ❤ by GitHub

복기

nr,nc를 사용해야 하는 부분에 r,c를 넣어놔서 한참을 헤맸다..

 

블로그의 첫 글인데, 계속 gitgub에만 문제풀이 코드를 올리다 보니 풀이 방법을 작성하는 것도 불편하고

정리해야 할 이론과 같은 것들을 github에 올리기는 힘들어서 시작한다.

이전에는 문제만 풀 수 있도록 소스코드를 다른 사람이 이해하기 어렵게 작성했는데, 아무래도 블로그는 외부에 노출되다 보니 좀 더 코드를 이해하기 쉽도록 작성하는 습관을 들여야겠다. 풀이도 좀더 명확히 알 수 있도록 작성해보자!