[Algorithm] 빙산 : 백준-2573

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

2573번: 빙산

 

전형적인 dfs 탐색 알고리즘이다.

 

구현을 다음과 같이 진행하였다.

 

먼저 필요한 배열을 다음과 같이 정의 하였다.

1. 전체적인 빙산의 위치를 나타내는 2차원 배열 map

2. 다음년도에 녹을 빙산의 위치를 나타내는 2차원 배열 melt

3. dfs 진행을 위해 방문한 위치를 표시하는 2차원 배열 visited

4. 전형적인 탐색을 위한 dx,dy

	int[][] map;
	int[][] melt;
	int[][] visited;
	int[] dx = {1,0,-1,0};
	int[] dy = {0,1,0,-1};

해당 문제는 먼저 맵에서 0이 아닌 숫자 인덱스에 왔을 때

해당 위치부터 상하좌우를 돌면서

방문하지 않은 0이 아닌 숫자가 존재한 맵을 계속해서 탐색한 후(연결된 빙산)

모두 방문 하였을때 빙산의 수를 1개씩 증가시키면서

맵을 모두 순회하면서 빙산의 수가 2개 이상일 때까지 반복문을 수행해 주면 된다.

 

	private static void solution(int row, int col) {
		int year = 0;
		while(true) {
			// 빙산 조각수
			int count=0;
			
			//탐색
			for(int i=0;i<row;i++) {
				for(int j=0; j<col; j++) {
					// 방문하지 않은 0이 아닌 곳에서 dfs수행
					if(visited[i][j]==0 && map[i][j]!=0) {
						dfs(row,col,i,j);
						// 빙산 조각+1
						count++;
						}
					}
			}
			if(count==0) {
				// 조각이 나눠지지 않고 모두 녹은 경우!
				System.out.println(0);
				break;
			}else if(count>=2) {
				// 2개 이상으로 빙산이 조각난 경우!
				System.out.println(year);
				break;
			}
			// count=1 인 경우는 현재 빙산이 1조각으로 구성되었다는 의미이다.
			melting(row,col);
			 // 아직 빙산이 1조각 이므로 내년으로 넘어감!
			year++;
		}
		
	}

 

다음은 dfs 매서드이다.

dfs 매서드는 현재 위치에서 상,하,좌,우 에 존재하는 0의 갯수만큼

다음해에 녹을 빙산의 높이를 melt 배열에 저장해 주는 역할을 한다.

 

	private static void dfs(int row, int col,int x,int y) {
		visited[x][y] = 1;
		// 4방향 체크
		for(int dir=0; dir<4; dir++) {
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			
			// 맵 안에 존재하는지 체크.
			if(nx>=0&&nx<row&&ny>=0&&ny<col) {
				//	주변 0 갯수만큼 내년에 녹음
				if(map[nx][ny]==0) {
					melt[x][y]++;
				}
				
				//dfs 수행
				// 아직 방문하지 않은 다음노드가 0이 아니면 수행
				if(visited[nx][ny]==0 && map[nx][ny]!=0)
					dfs(row,col,nx,ny);
			}
		}
	}

 

마지막으로 melting 매서드는 한번 순회후

melt 배열의 해당하는 좌표의 값만큼 map의 얼음을 녹여주는 역할을 한다.

여기서 조심할 점은 다시 순회를 하기 위해

melt배열과 visited 배열을 0으로 초기화 해줌과 동시에

map이 음수가 되는 예외를 처리해준다.

	private static void melting(int row, int col) {
		for(int i=0;i<row; i++) {
			for(int j=0; j<col; j++) {
				map[i][j] -= melt[i][j];
				//map 음수가 될시 0으로 만들어 준다.
				if(map[i][j]<0) {
					map[i][j]=0;
				}
				//다음 순회를 위한 초기화
				visited[i][j] = 0;
				melt[i][j]=0;
			}
		}
		
	}