[BOJ 16920] 확장 게임 (Java)

BOJ 16920 확장 게임

문제풀이

단순 BFS로 구현을 하면되겠지 했지만 많은 우여곡절을 겪은 문제다.

처음에는 시뮬레이션 문제 처럼 단순하게 다음과 같이 구현했다.
1. 현재 순서의 플레이어의 성을 모두 찾아서 큐에 넣는다.
2. 플레이어의 확장범위만큼 BFS 탐색하여 성을 건설한다.
3. 더 이상 확장할 수 없을 때 까지 반복한다.

하지만 턴이 진행될 때 마다 모든 성을 찾아서 넣는 부분이 시간을 많이 잡아먹어서 수정이 필요했다.

그래서 플레이어가 최대 9명으로 적기 때문에 게임 참여 플레이어 수 많큼 큐를 만들어 주는 방법을 선택했다.

Queue<Node>[] qs = new LinkedList[P + 1];
for(int i = 1 ; i <= P ; ++i) qs[i] = new LinkedList<>();

만족스럽게 구현하고서 제출했지만 시간초과... 코드를 아무리 살펴봐도 복잡도 때문에 시간초과가 나는것 같지는 않았다. 따라서 어딘가에 무한 루프가 존재하는 것이 아닌가하는 의문이 들었다. 계속해서 고민한 결과 찾아냈다.

처음 자료를 입력받을 때 빈칸의 갯수를 모두 세고 빈칸을 모두 채웠을 때 까지 반복하도록 하였는데 다음과 같은 케이스에서 무한루프를 발생시켰다.

4 4 2
1 1
1...
....
#...
.#.2

접근할 수 없는 빈칸이 계속 존재하기 때문에 종료 조건의 수정이 필요했다. 다음과 같이 수정하여 통과할 수 있었다.

• 한 라운드가 종료됐을 때 어떤 플레이어도 성을 확장하지 못했다면 더 이상 확장할 수 없는 것이다.

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static class Node {
		int r, c;
		
		Node(int r, int c){
			this.r = r;
			this.c = c;
		}
	}
	
	static Queue<Node>[] qs;
	static char[][] map;
	static int[] castle;
	static int[] distance;
	static int N, M, P;
	static int[][] dir = {{-1, 0}, {1, 0}, {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 = stoi(st.nextToken());
		M = stoi(st.nextToken());
		P = stoi(st.nextToken());
		
		map = new char[N][M];
		castle = new int[P + 1];
		distance = new int[P + 1];
		qs = new LinkedList[P + 1];
		
		for(int i = 1 ; i <= P ; ++i) qs[i] = new LinkedList<>();
		
		st = new StringTokenizer(br.readLine());
		for(int i = 1 ; i <= P ; ++i) distance[i] = stoi(st.nextToken());
		
		for(int i = 0 ; i < N ; ++i) {
			String line = br.readLine();
			for(int j = 0 ; j < M ; ++j) {
				char ch = line.charAt(j);
				
				if(ch >= '0' && ch <= '9') {
					int player = ch - '0';
		
					castle[player]++;
					qs[player].offer(new Node(i, j));
				}
				map[i][j] = ch;
			}
		}
		
		int player = 1;
		int round = 0;
		
		while(true) {
			int maxDist = distance[player];
			int cnt = expendCastle(qs[player], maxDist, player);
			
			castle[player] += cnt;
			round += cnt;
			
			player++;
			if(player == P + 1) {
				if(round == 0) break;
				round = 0;
				player = 1;
			}
		}
		
		for(int i = 1 ; i <= P ; ++i) System.out.print(castle[i] + " ");
	}

	private static int expendCastle(Queue<Node> q, int maxDist, int player) {
		int cnt = 0;
		int dist = 1;
		
		while(!q.isEmpty()) {
			int size = q.size();
			
			for(int i = 0 ; i < size ; ++i) {
				Node cur = q.poll();
				
				for(int d = 0 ; d < 4 ; ++d) {
					int nr = cur.r + dir[d][0];
					int nc = cur.c + dir[d][1];
					if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
					if(map[nr][nc] == '.') {
						q.offer(new Node(nr, nc));
						map[nr][nc] = (char)(player + '0');
						cnt++;
					}
				}
			}
			dist++;
			if(dist > maxDist) break;
		}

		return cnt;
	}

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