문제

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

구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위에 있다. 한 칸 위에 성이 두 개 이상인 경우는 없다.

게임은 라운드로 이루어져 있고, 각 라운드마다 플레이어는 자기 턴이 돌아올 때마다 성을 확장해야 한다. 제일 먼저 플레이어 1이 확장을 하고, 그 다음 플레이어 2가 확장을 하고, 이런 식으로 라운드가 진행된다.

각 턴이 돌아왔을 때, 플레이어는 자신이 가지고 있는 성을 비어있는 칸으로 확장한다. 플레이어 i는 자신의 성이 있는 곳에서 Si칸 만큼 이동할 수 있는 모든 칸에 성을 동시에 만든다. 위, 왼쪽, 오른쪽, 아래로 인접한 칸으로만 이동할 수 있으며, 벽이나 다른 플레이어의 성이 있는 곳으로는 이동할 수 없다. 성을 다 건설한 이후엔 다음 플레이어가 턴을 갖는다.

모든 플레이어가 더 이상 확장을 할 수 없을 때 게임이 끝난다. 게임판의 초기 상태가 주어졌을 때, 최종 상태를 구해보자.

---

입력

첫째 줄에 격자판의 크기 N, M과 플레이어의 수 P가 주어진다. 둘째 줄에는 S1, S2, ...SP가 주어진다.

다음 N개의 줄에는 게임판의 상태가 주어진다. '.'는 빈 칸, '#'는 벽, '1', '2', ..., '9'는 각 플레이어의 성이다.

모든 플레이어는 적어도 하나의 성을 가지고 있으며, 게임에 참가하지 않는 플레이어의 성이 있는 경우는 없다.

---

출력

플레이어 1이 가진 성의 수, 2가 가진 성의 수, ..., P가 가진 성의 수를 공백으로 구분해 출력한다.

---

풀이

접근방법

시간제한 2초, 메모리 512MB이다.
1 ≤ N, M ≤ 1,000
1 ≤ P ≤ 9
1 ≤ Si ≤ 10^9

전형적인 BFS를 활용하는 문제이다.
여러 플레이어로 인해 복잡해 보일수있으나, 순서대로 넣는다면 하나의 큐로 처리할 수 있다.

문제 자체는 단순하나, 생각하고 시작해야할 것들이 있다.

1. 플레이어의 이동거리가 최대 10^9.
2. 플레이어의 성을 확장하는 과정에서 다른성에 의해 막히는 경우.

문제에 접근을 해보자.
각 플레이어 별로 확장을 시작한다.
1번 플레이어의 모든 성을 최대 이동가능한 칸만큼 확장한다.
1번 플레이어가 더이상 확장할 수 없다면 2번 플레이어가 반복하여 진행한다.

1. 플레이어의 이동거리가 최대 10^9.

1. 플레이어의 성을 확장하는 과정에서 함수 스택을 사용하게 된다면, depth가 너무 깊어 dfs형식을 사용하기 어렵다.

2. 플레이어의 성을 확장하는 과정에서 다른성에 의해 막히는 경우.

조금 더 풀어서 설명하자면 아래와 같은 경우이다.

3 4 2
2 1
1...
1..2
....

1행 1열의 1이 먼저 확장을 모두 진행한다. 그렇다면 아래와 같이 변경된다.

111.
11.2
....

플레이어1의 성 2행 1열의 1이 다음으로 확장을 시작한다.
방문 체크를 하며 BFS를 이용해 탐색을 해나가는 과정에 문제가 발생한다.
2행2열의 1로 인해 우측으로 나아가는 방법이 Queue에 담기지 않는다.

<기존>		<비정상>		<정상>
111.		111.		111.
11.2	=>	11.2		1112
....		11..		11..

물론 처음부터 설계를 잘 하고 구현했다면, 위와같은 문제가 생기지도 않을 수 있다.
하지만 잘못된 설계로 진행을 해서 비정상과 같은 케이스가 발생했다면, 어떻게 접근하면 좋을지 다시 생각해보자.
코드를 덕지덕지 붙이면 시간초과를 만날뿐이다.

만약 비정상 -> 정상으로 변경하고 싶다면 어떤부분을 놓친걸까..
최초에 여러개의 성이 있다면,
하나의 성을 끝까지 확장하고, 다음성을 확장하는것이 아니라
여러개의 성을 동시에(같은 이동거리) 확장시켜나가면 된다.

---

코드

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

public class Main {
	static int N, M, P;
	static int[] maximumMove, area;
	static char[][] map;
	static List<Point>[] start;
	static Queue<Point> q;

	static final char BLANK = '.';
	static final char WALL = '#';

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

	static class Point {
		int x;
		int y;

		Point(int a, int b) {
			x = a;
			y = b;
		}
	}

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

		N = stoi(splitedLine[0]);
		M = stoi(splitedLine[1]);
		P = stoi(splitedLine[2]);
		maximumMove = new int[P + 1];
		area = new int[P + 1];
		map = new char[N][M];
		start = new List[P + 1];

		for (int i = 0; i < P + 1; ++i)
			start[i] = new ArrayList<>();

		splitedLine = in.readLine().split(" ");
		for (int i = 1; i <= P; ++i)
			maximumMove[i] = stoi(splitedLine[i - 1]);

		for (int i = 0; i < N; ++i) {
			String s = in.readLine();
			for (int j = 0; j < M; ++j) {
				map[i][j] = s.charAt(j);
				if ('1' <= map[i][j] && map[i][j] <= '9')
					start[map[i][j] - '0'].add(new Point(i, j));
			}
		}

		q = new ArrayDeque<>();
		// 1부터 모든 시작점을 넣어준다.
		for (int i = 1; i <= P; ++i)
			for (Point p : start[i])
				q.add(p);

		simulation();

		StringBuilder sb = new StringBuilder();

		// 각 플레이어의 성의 갯수를 찾는다.
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < M; ++j) {
				if ('1' <= map[i][j] && map[i][j] <= '9')
					area[map[i][j] - '0']++;
			}
		}

		for (int i = 1; i <= P; ++i)
			sb.append(area[i]).append(" ");

		System.out.println(sb);
	}

	private static void simulation() {
		while (!q.isEmpty()) {
			Point p = q.poll();
			int playerNum = map[p.x][p.y] - '0'; // 현재 진행중인 플레이어
			int maxMove = maximumMove[playerNum]; // 현재 플레이어의 최대 이동가능 범위

			Queue<Point> nextQ = new ArrayDeque<>();

			int[][] visit = new int[N][M];
			// 같은 플레이어의 성을 모두 넣는다.
			while (!q.isEmpty() && map[q.peek().x][q.peek().y] == map[p.x][p.y]) {
				visit[q.peek().x][q.peek().y] = 1;
				nextQ.add(q.poll());
			}

			nextQ.add(p);
			visit[p.x][p.y] = 1;
			while (!nextQ.isEmpty()) { // 특정 플레이어의 성을 최대 범위까지 확장한다.
				Point cur = nextQ.poll();
				for (int d = 0; d < 4; ++d) {
					int nextX = cur.x + dx[d];
					int nextY = cur.y + dy[d];
					if (isInRange(nextX, nextY) && visit[nextX][nextY] == 0 && map[nextX][nextY] == BLANK) {
						visit[nextX][nextY] = visit[cur.x][cur.y] + 1;
						map[nextX][nextY] = map[cur.x][cur.y];
						if (visit[nextX][nextY] == maxMove + 1) // 최대 범위까지 왔으면, 다른 플레이어가 진행 후 진행할 수 있다.
							q.add(new Point(nextX, nextY));
						else
							nextQ.add(new Point(nextX, nextY)); // 이동 가능횟수가 남아있다면, 현재 턴에 계속 확장한다.
					}
				}
			}
		}
	}

	private static boolean isInRange(int nextX, int nextY) {
		if (0 <= nextX && nextX < N && 0 <= nextY && nextY < M)
			return true;
		return false;
	}

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