31782 저체온증 [JAVA]

분석

 

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

 

N*M 배열에 O로 표시된 장소와 사방 중 2방이 인접하면 자신도 O가 되고

밤에는 최악의 경우로 K명이 다시 *이 된다.

 

수많은 낮과 밤에도 계속해서 낮에 O가되는 사람의 수를 구하는게 문제이다.

 

사실 어떤 패턴이 있을까 싶어 처음에 생각을 좀 해봤지만 딱히 특정 패턴을 찾기는 힘들었다.

다만, 시작하는 시점은 낮이라는 점을 고려해보면 생각보다 해결 방법은 간단했다.

 

예제 2번의 경우

O.....O
..O....
.O....O
.O...O.
......O

의 형태로 주어지는데

 

낮을 반영하게 되면

 

OOO..OO
OOO..OO
OOO..OO
OOO..OO
.....OO

이렇게 된다.

 

여기서 1명을 어떤 식으로 .으로 바꿔도 다시 낮에 O이 된다.

하지만, 여기서 2명을 제거해보자

왼쪽 3x4 직사각형에선 어떤 방식으로든 다시 낮에 3x4의 직사각형이 유지되지만

오른쪽 2x6직사각형에선 맨 위든 맨 아래든 2명을 .으로 돌리면 다시 낮이 와도 .이 된 2명은 O이 되지 못한다.

동일한 이유로 2x6 직사각형은 총 6번의 밤으로 모두 .이 된다.

 

즉, 우리는 첫 날 낮에 생기는 여러 직사각형들에 대해서

각 직사각형의 min(가로,세로) 가 K보다 큰 직사각형만 계속해서 살아남을 수 있기 때문에 이러한 직사각형의 넓이의 합을 리턴하면 된다.

 

코드

 

import java.io.*;
import java.util.*;

public class Main {

	static boolean[][] isNormal;
	static boolean[][] isVisited;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};

	static int n,m,k;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] s = sc.nextLine().split(" ");
		if(s.length != 3)
			throw new RuntimeException("Invalid Input");

		n = Integer.parseInt(s[0]);
		m = Integer.parseInt(s[1]);
		k = Integer.parseInt(s[2]);

		// n = m = 2000;
		// k = 1999;

		isNormal = new boolean[n][m];

		for (int i = 0; i < n; i++) {
			char[] charArray = sc.nextLine().toCharArray();
			for (int j = 0; j < charArray.length; j++) {
				isNormal[i][j] = charArray[j] == 'O';
			}

			// for (int j = 0; j < m; j++) {
			// 	isNormal[i][j] =  Math.random()> 0.95;
			// }
		}



		//first day
		isVisited = new boolean[n][m];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(!isNormal[i][j])
					continue;

				Queue<Point> points = new LinkedList<>();
				points.add(new Point(i,j));

				while (!points.isEmpty()){
					Point poll = points.poll();
					if(isVisited[poll.x][poll.y])
						continue;
					isVisited[poll.x][poll.y]=true;
					for (int l = 0; l < 4; l++) {
						int nx = poll.x+dx[l];
						int ny = poll.y+dy[l];
						if(nx<0 || ny <0 || nx>=n || ny >= m)
							continue;
						if(!isNormal[nx][ny])
							isNormal[nx][ny] = canBeNormal(nx,ny);

						if(isNormal[nx][ny] && !isVisited[nx][ny])
							points.add(new Point(nx,ny));
					}
				}
				// tryMakeNormal(i,j);
			}
		}

		isVisited = new boolean[n][m];
		int ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(isNormal[i][j] && !isVisited[i][j]){
					//left top
					int height = 1;
					for (int l = i+1; l < n; l++) {
						if(!isNormal[l][j])
							break;
						height++;
					}

					int width = 1;
					for (int l = j+1; l < m; l++) {
						if(!isNormal[i][l])
							break;
						width++;
					}

					for (int l = 0; l < height; l++) {
						for (int o = 0; o < width; o++) {
							isVisited[i+l][j+o] = true;
						}
					}

					if(Math.min(height,width) > k){
						ans += height*width;
					}


				}
			}
		}

		System.out.println(ans);
	}

	private static void tryMakeNormal(int i, int j) {
		if(isNormal[i][j])
			return;
		isVisited[i][j] = true;

		int normalCount = 0;

		for (int k = 0; k < 4; k++) {
			int nx = i+dx[k];
			int ny = j+dy[k];
			if(nx<0 || ny <0 || nx>=n || ny >= m)
				continue;

			if(!isNormal[nx][ny] && !isVisited[nx][ny])
				tryMakeNormal(nx,ny);

			if(isNormal[nx][ny])
				normalCount++;
		}
		if(normalCount>=2)
			isNormal[i][j]=true;
	}

	static boolean canBeNormal(int i, int j){
		int normalCount = 0;
		for (int k = 0; k < 4; k++) {
			int nx = i+dx[k];
			int ny = j+dy[k];
			if(nx<0 || ny <0 || nx>=n || ny >= m)
				continue;

			if(isNormal[nx][ny])
				normalCount++;
		}
		return normalCount >= 2;
	}

	static class Point{
		int x,y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

 

첫 낮을 구하는 과정에서 처음에는 재귀로 구현을 했으나 (tryMakeNormal) 시간도 많이 걸리고 배열 초기화를 매 iter에 하기엔 반복의 수가 많아 bfs로 변경했다.

 

코드는

input받기 -> 첫날 낮의 상태를 만들기 -> min(가로,세로) > k인 직사각형의 넓이를 ans에 더하기

의 흐름으로 이어진다.