16569. 화산쇄설류

문제 링크

1. 문제 해설

문제의 규칙을 살펴보자.

1. 재상이는 처음에 X행 Y열에 있다.
2. 재상이는 단위 시간 당 상하좌우 한 칸만 움직일 수 있다.
3. 재상이는 화산이 있는 위치와 화산쇄설류가 뒤덮인 곳은 갈 수 없다.
4. 어떤 화산의 위치를 (x, y), 폭발을 시작한 시각을 t 라고 하자. t+δ 시각이 되면 δ ≥ |u-x|+|v-y|인 모든 (u, v)위치의 지대들은 높이 무관하게 화산쇄설류가 덮치게 된다.

따라서 필자는 위의 규칙을 표현하기 위해 아래와 같이 진행하였다.

1. 전처리 과정으로 화산과 화산쇄설류를 표현한다.
2. 재상의 위치를 기준으로 상하좌우를 움직인다.

하나하나씩 살펴보자.

1-1. 전처리 과정으로 화산과 화산쇄설류를 표현

재상이는 화산과 화산쇄설류로 덮은 지역을 가지 못한다.
따라서, 재상이가 움직이기 전에 미리 화산과 화산쇄설류로 덮히는 지역을 표시한다.

우선, 화산을 뜻하는 Volcano 객체로 된 이차원 배열을 크기 (m,n)으로 하여 생성한다.

Volcano 객체는 아래의 필드를 가지고 있다.

1. 현재 고도
2. 화산쇄설류가 덮는 최소 시간

2번의 최소 시간을 저장하는 이유는 문제에 명시된 t+δ 시각이 되면 δ ≥ |u-x|+|v-y|인 모든 (u, v)위치의 지대들은 높이 무관하게 화산쇄설류가 덮치게 된다. 조건 때문이다.

따라서, V번 반복하면서 (i,j)의 위치는 화산이므로 최소 시간은 0이고 나머지 위치는 t + |u-i| + |v-j|를 진행하며 (u,v)에 최소 시간을 넣는다.

1-2. 재상이의 위치를 기준으로 상하좌우 이동

재상이는 단위 시간에 상,하,좌,우 중 한 곳으로만 이동이 가능하다.

주의해야 할 점은 큐를 이용하여 BFS를 진행하는데 큐 하나가 현재 시간에 재상이가 이동할 수 있는 모든 경우 인 점이다.

만약, 재상이가 현재 시각(t)초에 (i,j)에서 상하좌우로 이동했다면 상하좌우 모두 t초에 이동했다는 의미이다.

따라서, 아래와 같이 진행한다.

1. 현재 큐(q)에 있는 값을 이용하여 재상이가 움직일 수 있는 좌표를 찾고 q에 넣는게 아니라 임시 큐(tq)에 넣는다.
2. 현재 시간을 증가 시킨다.
3. 임시 큐(tq)에 있는 좌표를 다시 현재 큐(q)에 넣고 1번으로 되돌아간다.

1-3. 15%에서 "틀렸습니다."

15% 틀린 코드는 아래와 같다.

...
int ansTime = 0, ansHeight = 0; //문제가 되는 코드
...

만약, m과 n이 1,1 일 경우, 해당 고도가 0이면 문제가 되지 않지만 그 외 값 일 경우 재상이의 시작 지점과 동일하므로 ansHeight가 문제 된다.

따라서, 코드를 아래와 같이 수정하여 재상이의 시작 지점 고도를 초기값으로 설정하여 진행해야 된다.

...
int ansTime = 0, ansHeight = vol[x][y].height; //수정된 코드
...

2. 소스 코드

//화산쇄설류
import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		int V = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		int X = Integer.parseInt(st.nextToken());
		int Y = Integer.parseInt(st.nextToken());

		Volcano[][] vol = new Volcano[M][N];

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int height = Integer.parseInt(st.nextToken());

				vol[i][j] = new Volcano(height, Integer.MAX_VALUE);
			}
		}

		// x,y 지점의 화산을 기준으로 최소 시간을 구한다.
		for (int i = 0; i < V; i++) {
			st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			int t = Integer.parseInt(st.nextToken());
			for (int j = 0; j < M; j++) {
				for (int k = 0; k < N; k++) {
					if (x == j && k == y)
						vol[j][k].time = 0;
					else {
						int lam = Math.abs(x - j) + Math.abs(y - k);
						vol[j][k].time = Math.min(vol[j][k].time, t + lam);
					}
				}
			}
		}

		simulation(X - 1, Y - 1, M, N, vol);
	}

	private static void print(Volcano[][] vol, int x, int y) {
		System.out.println();
		for (int i = 0; i < vol.length; i++) {
			for (int j = 0; j < vol[i].length; j++) {
				if (x == i && y == j) {
					System.out.print("T" + " ");
				} else
					System.out.print(vol[i][j].time + " ");
			}
			System.out.println();
		}
	}

	private static void simulation(int x, int y, int m, int n, Volcano[][] vol) {
		int currentTime = 1;
		int[] ud = { -1, 0, 1, 0 };
		int[] rl = { 0, 1, 0, -1 };

		boolean[][] visited = new boolean[m][n];

		Queue<Point> q = new LinkedList<>();
		q.add(new Point(x, y));
		visited[x][y] = true;

		int ansTime = 0, ansHeight = vol[x][y].height;

		while (!q.isEmpty()) {
			Queue<Point> temp = new LinkedList<>(q);
			q.clear();
			// System.out.print("\nCurrent Time: " + currentTime);
			while (!temp.isEmpty()) {
				Point cur = temp.poll();

				//print(vol, cur.x, cur.y);
				for (int i = 0; i < 4; i++) {
					int nx = cur.x + ud[i];
					int ny = cur.y + rl[i];

					// 배열을 벗어난 경우
					if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx][ny])
						continue;

					if (vol[nx][ny].time > currentTime) {
						// 화산쇄설류가 덮기 전일 경우
						if (ansHeight < vol[nx][ny].height) {
							ansHeight = vol[nx][ny].height;
							ansTime = currentTime;
						}
						visited[nx][ny] = true;
						q.add(new Point(nx, ny));
					}
				}
			}

			currentTime++; // 시간 증가
		}

		System.out.println(ansHeight + " " + ansTime);
	}

	private static class Point {
		int x, y;

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

	private static class Volcano {
		int height, time;

		public Volcano(int h, int t) {
			this.height = h;
			this.time = t;
		}
	}
}