[백준_5212번] 지구 온난화

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

5212번: 지구 온난화

[문제]

 푸르고 아름다운 남해에는 많은 섬이 장관을 이루고 있다. 그림이 아니면 볼 수 없을 것 같은 아름다운 장관을 실제로 볼 수 있는 다도해로 상근이는 여행을 떠났다. 다도해에 도착한 상근이는 서울에서 보던 것과는 다른 풍경에 큰 충격을 받았다. 지구 온난화로 인해 해수면이 상승해 섬의 일부가 바다에 잠겨버렸다. 서울로 다시 돌아온 상근이는 이렇게 지구 온난화가 계속 될 경우 남해의 지도는 어떻게 바뀔지 궁금해졌다.

다도해의 지도는 R*C 크기의 그리드로 나타낼 수 있다. 'X'는 땅을 나타내고, '.'는 바다를 나타낸다. 50년이 지나면, 인접한 세 칸 또는 네 칸에 바다가 있는 땅은 모두 잠겨버린다는 사실을 알았다. 상근이는 50년 후 지도를 그려보기로 했다. 섬의 개수가 오늘날보다 적어질 것이기 때문에, 지도의 크기도 작아져야 한다. 지도의 크기는 모든 섬을 포함하는 가장 작은 직사각형이다. 50년이 지난 후에도 섬은 적어도 한 개 있다. 또, 지도에 없는 곳, 지도의 범위를 벗어나는 칸은 모두 바다이다.

 

[입력 조건]

첫째 줄에 지도의 크기 R과 C (1 ≤ R, C ≤ 10)가 주어진다. 다음 R개 줄에는 현재 지도가 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_5212 {
	static char[][] map;
	static int[][] nummap; // 주변의 육지 개수를 count 하는 배열
	static int[] dx= {-1,1,0,0};
	static int[] dy= {0,0,-1,1};
	static int r,c;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		r=sc.nextInt();
		c=sc.nextInt();
		
		map=new char[r][c];
		nummap=new int[r][c];
		
		// 지도 상태 입력받기 
		for(int i=0;i<r;i++) {
			String str=sc.next();
			for(int j=0;j<c;j++) {
				map[i][j]=str.charAt(j);
			}
		}
		
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				char ch=map[i][j];
				int count=0; // 주변의 육지 개수 count
				
				// 바다인 경우는 무시
				if(ch=='.')
					continue;
				
				// 육지인 경우 해당 좌표로부터 상,하,좌,우 탐색
				else {
					for(int k=0;k<4;k++) {
						int nx=i+dx[k];
						int ny=j+dy[k];
						
						// 이동 좌표가 범위 내에 있고, 육지라면 count
						if(nx>=0&&ny>=0&&nx<r&&ny<c) {
							if(map[nx][ny]=='X')
								count++;
						}
					}
				}
				nummap[i][j]=count; // 해당 좌표 4 방향의 육지 개수를 저장한다.
			}
		}
		
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				/*
				 * 주변에 육지의 개수가 1개 이하라면 
				 * 3면 이상이 바다이기 때문에 해당 좌표 바다로 변경
				 */
				if(nummap[i][j]<2)
					map[i][j]='.';
			
			}		
		}
		
		/*
		 * 새롭게 출력해야 하는 지도는 모든 섬을 포함하는 가장 작은 직사각형이어야 하기 때문에
		 * 육지가 있는 x,y 좌표의 각각 최대, 최솟 값을 찾아 그 범위만큼의 지도를 출력하면 된다.   
		 */
		int lx=Integer.MAX_VALUE;
		int ly=Integer.MAX_VALUE;
		int rx=Integer.MIN_VALUE;
		int ry=Integer.MIN_VALUE;
		
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				if(map[i][j]=='X') {
					lx=Math.min(i, lx);
					ly=Math.min(j, ly);
					rx=Math.max(i, rx);
					ry=Math.max(j, ry);
				}
			}
		}
		
		// 지도 출력
		for(int i=lx;i<=rx;i++) {
			for(int j=ly;j<=ry;j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
	}
}

 

[고찰]

 이번 문제는 시뮬레이션 카테고리로 주어진 조건을 빠짐 없이 구현하면 되는 문제였다. 처음에는 육지를 기점으로 4방향에 바다가 몇개인지 count 했었다. 하지만 지도의 범위를 벗어난 곳도 바다이기 때문에 외각에 있는 육지에서 바다의 개수를 셀 경우 범위 이외의 곳도 탐색해야 하는 과정에서 자꾸 배열 인덱스 오류가 났었다. 

 그래서 방법을 바꿨다. 육지의 개수가 3개 이상인 경우 해당 지점은 바다로 변경해야한다는 의미는 곧 상, 하, 좌, 우 4방향 중 육지의 개수가 1개 이하라면 바다로 변경해야한다는 것과 같은 의미이다. 이런 방법으로 바꾸니 배열의 인덱스를 넘어가는 오류 없이 문제를 해결할 수 있었다.