문제

https://www.codetree.ai/training-field/frequent-problems/problems/magical-forest-exploration/description?page=1&pageSize=20

---

입력

첫 번째 줄에는 숲의 크기를 의미하는 R, C, 정령의 수 K가 공백을 사이에 두고 주어집니다.

그다음 줄부터 K개의 줄에 거쳐 각 골렘이 출발하는 열 c, 골렘의 출구 방향 정보 d가 공백을 사이에 두고 주어집니다.

---

출력

첫 번째 줄에 각 정령들이 최종적으로 위치한 행의 총합을 출력하세요.

---

풀이

제한조건

• 5 ≤ R,C ≤ 70
• 1 ≤ K ≤ 1000
• 2 ≤ c ≤ C−1
• 0 ≤ d ≤ 3

접근방법

시뮬레이션

문제분석

문제를 읽어보며 어떤 형태로 시뮬레이션이 반복되며,
주의할 점은 무엇이고 어떤 함수들을 만들어야 할 지 생각해보자.

골렘이 아래,.왼쪽, 오른쪽 방향으로 이동할 수 있기 때문에 이동에 따라서 격자 밖으로 나가는지 체크해야 한다.
그리고 마지막 조건을 검사하기위해 골렘이 숲내부인지 확인할 수 있는 함수도 필요하다.

아래 3개의 기능에 유의하며 진행해보자.

- 골렘의 이동 가능 여부
- 정령의 최대 행
- 골렘이 숲의 내부에 있는지 확인

우선 최초 시작에서 골렘이 격자 밖에서 시작한다.
이것을 코드로 표현하기 위해서는 R x C 로 표현할 것이 아니라
(R+3) x C 으로 표현해야 한다.

e.g) 5행 7열의 숲의 위쪽에 3칸을 추가해서 생성 => 8행 7열

이제 테트리스 처럼 골렘을 아래로 내리면 된다.

- 골렘의 이동가능 여부 확인
골렘이 이동할 때, 확인해야 하는 칸은 항상 정해져 있다.
각 골렘이 좌,하,우 방향으로 이동할 때, 초록색 칸이 항상 비어있어야 한다.

- 정령의 최대 행
골렘이 움직일 수 없다면, 최대 행을 계산해야 한다.
이때 최대행은 골렘의 중심좌표+1 또는 출구와 인접한 골렘의 최대 좌표를 따라간다.

최대행을 찾는 방법은 여러가지가 있는데,
서로소 집합처럼 최대행을 가지는 것을 부모로 관리하면 빠르게 최대행을 찾을 수 있다.
다만 단점은 추후에 다른 골렘에 의해 최대값이 변경될 수 있어 별도의 처리가 필요하다.

다른 방법은 골렘의 이동이 종료될 때, 탐색을 통해서 최대행을 계속 계산해주는 방법이다.

시뮬레이션 문제이기 때문에 이제 차근차근 작성하면 끝이다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.List;
import java.util.Queue;

public class Main {
	static class Unit {
		int id;
		int x;
		int y;
		int dir;

		Unit(int id, int x, int y, int dir) {
			this.id = id;
			this.x = x;
			this.y = y;
			this.dir = dir;
		}
	}

	static Unit[] units;
	static int R, C, K, result;
	static int[][] arr; // 전체 map
	static int[][] exitMap;
	static int[] maxRowValue;
	static int[] parent;

	// 출구 방향 전환용
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};

	// 아래 이동
	static int[] tx = {2, 1, 1};
	static int[] ty = {0, -1, 1};

	// 왼쪽 아래 이동
	static int[] lx = {0, 1, -1, 1, 2};
	static int[] ly = {-2, -1, -1, -2, -1};

	// 오른쪽 아래 이동
	static int[] rx = {0, 1, -1, 1, 2};
	static int[] ry = {2, 1, 1, 2, 1};

	// 인접 범위
	static int[] ex = {-2, -1, 0, 1, 2, 1, 0, -1};
	static int[] ey = {0, 1, 2, 1, 0, -1, -2, -1};

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader((System.in)));
		String[] inputs = in.readLine().split(" ");

		R = stoi(inputs[0]);
		C = stoi(inputs[1]);
		K = stoi(inputs[2]);

		initMap();
		maxRowValue = new int[K + 1];
		parent = new int[K + 1];
		for (int i = 0; i <= K; ++i)
			parent[i] = i;
		units = new Unit[K + 1];

		result = 0;
		for (int i = 1; i <= K; ++i) {
			inputs = in.readLine().split(" ");
			units[i] = new Unit(i, 1, stoi(inputs[0]) - 1, stoi(inputs[1]));
			simulation(units[i]);
		}

		System.out.println(result);
	}

	/**
	 * 초기화
	 */
	private static void initMap() {
		arr = new int[R + 3][C];
		exitMap = new int[R + 3][C];
	}

	/**
	 * 각 골렘에 대해서 시뮬레이션 진행
	 */
	private static void simulation(Unit unit) {
		while (true) {
			// 아래로 이동할 수 있다면 아래로 이동한다.
			if (canMove(unit, tx, ty)) {
				unit.x++;
				continue;
			}

			// 왼쪽으로 이동할 수 있다면 왼쪽으로 이동한다.
			if (canMove(unit, lx, ly)) {
				// 출구의 방향 변경 필요
				unit.dir = (unit.dir + 3) % 4;
				unit.x++;
				unit.y--;
				continue;
			}

			// 오른쪽으로 이동할 수 있다면 오른쪽으로 이동한다.
			if (canMove(unit, rx, ry)) {
				unit.dir = (unit.dir + 1) % 4;
				unit.x++;
				unit.y++;
				continue;
			}

			// 이동이 불가능하다. 중단
			break;
		}

		// 만약, 몸 일부가 숲의 밖이라면 맵을 초기화 한다.
		if (isOut(unit)) {
			initMap();
			return;
		}

		// 표시
		exitMap[unit.x + dx[unit.dir]][unit.y + dy[unit.dir]] = unit.id;
		arr[unit.x][unit.y] = unit.id;
		for (int d = 0; d < 4; ++d)
			arr[unit.x + dx[d]][unit.y + dy[d]] = unit.id;

		// 계산
		maxRowValue[unit.id] = unit.x - 1;

		int exitX = unit.x + dx[unit.dir];
		int exitY = unit.y + dy[unit.dir];
		for (int d = 0; d < 4; ++d) {
			int nx = exitX + dx[d];
			int ny = exitY + dy[d];
			if (isInRange(nx, ny) && arr[nx][ny] != 0) {
				if (arr[nx][ny] == unit.id)
					continue;
				int n = arr[nx][ny];
				if (maxRowValue[n] > maxRowValue[unit.id]) {
					maxRowValue[unit.id] = maxRowValue[n];
					parent[unit.id] = find(parent[n]);
				}
			}
		}

		result += maxRowValue[unit.id];

		// 현재의 골렘에 의해, 이후 exitRow 에 영향이 있을 수 있다.
		boolean[] check = new boolean[K + 1];
		check[unit.id] = true;
		Queue<Integer> q = new ArrayDeque<>();
		q.add(unit.id);
		while (!q.isEmpty()) {
			int id = q.poll();
			for (int d = 0; d < 8; ++d) {
				int nx = units[id].x + ex[d];
				int ny = units[id].y + ey[d];
				if (isInRange(nx, ny) && exitMap[nx][ny] != 0 && !check[exitMap[nx][ny]]) {
					int near = exitMap[nx][ny];
					check[near] = true;
					q.add(near);
					if (maxRowValue[unit.id] > maxRowValue[near]) {
						parent[near] = find(parent[unit.id]);
						maxRowValue[near] = maxRowValue[unit.id];
					}
				}
			}
		}
	}

	/**
	 * 부모를 찾는다.
	 */
	private static int find(int n) {
		if (parent[n] == n)
			return n;
		else
			return parent[n] = find(parent[n]);
	}

	/**
	 * 골렘이 이동가능한 격자 내부에 있는가?
	 */
	private static boolean isInRange(int x, int y) {
		if (0 <= x && x < R + 3 && 0 <= y && y < C)
			return true;
		return false;
	}

	/**
	 * 골렘이 숲의 내부에 위치하는가?
	 */
	private static boolean isInForest(int x, int y) {
		if (3 <= x && x < R + 3 && 0 <= y && y < C)
			return true;
		return false;
	}

	/**
	 * 골렘이 특정 방향으로 이동가능한가?
	 */
	private static boolean canMove(Unit unit, int[] xArr, int[] yArr) {
		int len = xArr.length;
		for (int d = 0; d < len; ++d) {
			int nx = unit.x + xArr[d];
			int ny = unit.y + yArr[d];
			if (!(isInRange(nx, ny) && arr[nx][ny] == 0))
				return false;
		}
		return true;
	}

	private static boolean isOut(Unit unit) {
		for (int d = 0; d < 4; ++d) {
			if (!isInForest(unit.x + dx[d], unit.y + dy[d]))
				return true;
		}
		return false;
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}