[Softeer/소프티어][Level3]동계 테스트 시점 예측(Java)

https://softeer.ai/practice/info.do?idx=1&eid=411

Softeer

[문제]

북위 65도. 스웨덴의 소도시 아르예플로그(Arjeplog)에 자리한 동계 테스트 센터. 겨울 내내 얼음 두께가 1M 내외로 유지되는 광할한 얼음 호수와 그냥 걷기조차 힘든 눈길을 무대로 현대자동차그룹 연구원들은 극한 환경 속에서 더 나은 차량 성능을 확보하기 위해 제동안정성, 주행안정성, ADAS 기능 등에 대한 다양한 평가를 숨가쁘게 이어가고 있다.

이 곳은 기온이 너무 추워서 아침에 출근해보면 테스트 차량들 위에 큰 눈얼음이 생겨 있다. 정상적인 테스트를 위해서는 커다란 얼음이 어느정도 녹고 난 뒤에 가능한데, 차량 마다 당일의 테스트 가능 시점을 알기 위한 예측 프로그램을 제작 중에 있다. 

예측 프로그램은 N×M (5 ≤ N, M ≤ 100)의 격자 화면 위에 눈 얼음의 모양을 작은 정사각형들이 집합되어 있는 모양으로 변환하여 위 그림과 같이 표시해 준다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 얼음은 아침이 되면 기온이 상승하여 천천히 녹는다.

그런데 화면에서 나타난 얼음의 모양은 작은 정사각형 모양의 4변 중에서 적어도 2변 이상이 외부의 공기와 접촉했을 때 정확히 한 시간 만에 녹아 없어져 버린다. 따라서 위 그림의 모양과 같은 얼음(파란으로 표시된 부분)라면 C로 표시된 모든 얼음 격자는 한 시간 후에 사라진다.

위와 같이 얼음 내부에 있는 공간은 얼음 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므로 이 공간에 접촉한 얼음 격자는 녹지 않고 C로 표시된 얼음 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면, 아래 그림에서와 같이 C로 표시된 얼음 격자들이 사라지게 된다.

격자 화면의 맨 가장자리에는 얼음이 놓이지 않는 것으로 가정한다. 입력으로 주어진 얼음이 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성해보자. 

 

[풀이]

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

class LocationICE
{
	int row;
	int col;
	
	public LocationICE(int nCol, int nRow)
	{
		col = nCol;
		row = nRow;
	}
}


public class Main
{
   
	
	static int N; // 5 <= N
	static int M; // M <= 100
	static int MAP[][];
	static int VISITED[][];
	static int TIME = 0;
	static Queue<LocationICE> queue = new LinkedList<>();
	
	static int[] DX = { -1, 0, 1, 0 };
	static int[] DY = { 0, -1, 0, 1 };
	
	public static void main(String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		MAP = new int[N][M];
		VISITED = new int[N][M];
		
		for (int i = 0; i < N; i++)
		{
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++)
			{
				MAP[i][j] = Integer.parseInt(st.nextToken());
//				VISITED[i][j] = 0;
			}
		}
		
		while (true)
		{
			boolean bFoundIce = false;
			clear();
			for (int i = 0; i < N; i++)
			{
				for (int j = 0; j < M; j++)
				{
					if (MAP[i][j] == 1)
					{
						bFoundIce = true;
						BFS();
					}
				}
			}
			if (!bFoundIce)
				break;
			TIME++;
		}
		
		System.out.println(TIME);
	}
	
	private static void clear()
	{
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (VISITED[i][j] >= 2)
					MAP[i][j] = 0;
				
				VISITED[i][j] = 0;
			}
		}
	}
	
	private static void BFS()
	{
		queue.add(new LocationICE(0, 0));
		while (!queue.isEmpty())
		{
			LocationICE locIce = queue.poll();
			int col = locIce.col;
			int row = locIce.row;
			
			VISITED[col][row] = 1;
			
			for (int i = 0; i < 4; i++)
			{
				int x = col + DX[i];
				int y = row + DY[i];
				
				if (x < 0 || x >= N || y < 0 || y >= M)
					continue;
				
				if (MAP[x][y] == 1) // 얼음이라면
				{
					VISITED[x][y] += 1;
				} else if (VISITED[x][y] == 0)
				{
					queue.add(new LocationICE(x, y));
					VISITED[x][y] = 1;
				}
			}
		}
	}
}