문제 정리

---

r x c 지도에서 X는 땅이고 .는 바다일 때
상하좌우 3칸 이상이 바다인 땅은 50년 후에 물에 잠긴다고 한다
지도의 범위 밖은 바다로 간주한다

50년 후의 지도를 출력하되
모든 땅을 포함하는 가장 작은 직사각형만 출력한다

입력

R C
지도 정보

출력

50년 후의 지도

idea 정리

---

나는 배열을 다 돌면서 체크해야되는 문제가 나오면
체크가 필요한 것들은 q에 넣어놓고 빼서 계산하고 조건에 따라 다시 넣는 방식을 선호한다
이 문제도 그렇게 처리했다

가라앉는 땅의 경우는 direction 배열을 돌면서 바다의 개수를 카운트 해주면 된다, 배열의 범위밖도 바다로 카운트 해준다

주변 바다의 수를 카운트 해줄때 조심해야할 것은
먼저 계산한 땅이 가라앉을 경우까지 바다로 카운트하지 않도록 조심하는것이 중요하다

가장 직사각형 범위를 구해주는 것은 남은 땅 중 min, max 값만 가져와서 출력에 사용하면 된다

알고리즘 구성

---

1. 땅인 경우 q에 넣어줌
2. q에 있는 땅들을 하나씩 빼서 가라앉는지 계산
   2-1. 가라앉을 경우 바다와 다르게 표시
   -> 다른 땅 계산시 바다로 카운트 하지 않기 위해
3. 남은 q중 배열의 행, 열의 min, max를 구해준다
4. 3에서 구한 min,max 범위의 지도를 출력한다
   -> 가라앉은 땅은 바다로 출력해야함

구현

---

//지구 온난화
public class Main {
	static class Point {
		int r, c;

		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
	}

	static Queue<Point> q = new LinkedList<>();
	static int R, C;
	static char[][] map;

	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[R][C];

		for (int i = 0; i < R; i++) {
			char[] arr = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				char c = arr[j];
				map[i][j] = c;
				if (c == 'X') {
					q.add(new Point(i, j));
				}
			}
		}

		for (int i = 0, size = q.size(); i < size; i++) {		//50년만 계산하면 되므로 q size만큼만
			Point now = q.poll();
			int cnt = 0;

			for (int d = 0; d < 4; d++) {
				int nr = now.r + dr[d];
				int nc = now.c + dc[d];

				if (0 <= nr && nr < R && 0 <= nc && nc < C) {
					if (map[nr][nc] == '.')
						cnt++;
				}
				else cnt++;
			}
			if (cnt >= 3)    //후에 카운트 되지 않도록
				map[now.r][now.c] = '-';  
			else
				q.add(now);
		}
		
		List<Point> list = new ArrayList<>(q);
		
		int minR=R, maxR=0, minC=C, maxC=0;
		for(int i=0, size=list.size(); i<size; i++) {
			Point now = list.get(i);
			minR = Math.min(now.r, minR);
			maxR = Math.max(now.r, maxR);
			minC = Math.min(now.c, minC);
			maxC = Math.max(now.c, maxC);
		}
		
		for(int i=minR; i<=maxR; i++) {   //지도 출력
			for(int j=minC; j<=maxC; j++) {
				char c = map[i][j];
				if(c=='-') {    //가라앉은 땅인 경우 바다로 출력
					bw.write('.');
				}
				else {
					bw.write(c);
				}
			}
			bw.write("\n");
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
}

결과

---