[백준 BOJ] 16920. 확장 게임

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

문제 정리

N x M 짜리 격자판 위에서 플레이어 P명이 게임을 한다.
매 라운드마다 플레이어 1부터 오름차순으로 턴이 진행되는데, 각 턴에 플레이어 i는 최대 S_i 만큼 이동해서 도달할 수 있는 모든 칸으로 확장 한다.
더 이상 확장할 수 있는 플레이어가 없을 때 게임을 종료하고 그 때의 상태를 구한다.

정답 코드

import java.util.*;
import java.io.*;
public class Main {
	static int[][] a;
	static boolean[][] c;
	static int[] s;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	static int n,m,p;
	static int[] ans;
	static final int MAX = 1000000;
	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());
		p = Integer.parseInt(st.nextToken());
		a = new int[n][m];
		c = new boolean[n][m];
		s = new int[p+1];
		ans = new int[p+1];
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=p; i++) {
			s[i] = Integer.parseInt(st.nextToken());
			if(s[i]>MAX) s[i] = MAX;
		}
		LinkedList<Pair>[] list = new LinkedList[p+1];
		for(int i=1; i<=p; i++) list[i] = new LinkedList<Pair>();
		for(int i=0; i<n; i++) {
			String in = br.readLine();
			for(int j=0; j<m; j++) {
				char ch = in.charAt(j);
				if(ch == '#') {
					a[i][j] = -1;
				}else if(ch == '.') {
					a[i][j] = 0;
				}else {
					a[i][j] = ch-'0';
					list[a[i][j]].add(new Pair(i,j));
					ans[a[i][j]]++;
				}
			}
		}
		while(true) {
			for(int i=1; i<=p; i++) {
				int e = 0;
				while(list[i].size() > 0) {
					int ls = list[i].size();
					while(ls-- > 0) {
						Pair p = list[i].poll();
						for(int k=0; k<4; k++) {
							int ni = p.i + dx[k];
							int nj = p.j + dy[k];
							if(ni < 0 || ni >=n || nj < 0 || nj >= m) continue;
							if(a[ni][nj] != 0) continue;
							ans[i]++;
							list[i].add(new Pair(ni,nj));
							a[ni][nj] = i;
						}
					}
					e++;
					if(e == s[i]) break;
				}
			}
			boolean ok = true;
			for(int i=1; i<=p; i++) {
				if(list[i].size() > 0) ok = false;
			}
			if(ok) break;
		}
		for(int i=1; i<=p; i++) {
			System.out.print(ans[i]);
			if(i != p) System.out.print(' ');
		}
	}
	static class Pair{
		int i, j;
		public Pair(int i, int j) {
			this.i = i;
			this.j = j;
		}
	}
	static class Cas{
		int len, i, j;
		public Cas(int len, int i, int j) {
			this.len = len;
			this.i = i;
			this.j = j;
		}
	}
}

오답 노트

처음 문제를 풀었을 때 일반적인 BFS 문제와 똑같이 하나의 queue를 사용해 확장해야할 좌표를 저장했다.

LinkedList<Pnt> list = new LinkedList<Pnt>();

이 때 사용된 Pnt 클래스는 플레이어 번호도 가지고 있다.

	static class Pnt{
		int pl, i, j;
		public Pnt(int pl, int i, int j) {
			this.pl = pl;
			this.i = i;
			this.j = j;
		}
	}

이렇게 문제를 푸니 틀렸습니다 를 받았는데,

그 이유는 queue를 하나만 사용해서 넣어주게 되면 한 플레이어가 가진 여러 성이 한 턴에서 확장을 할 때 서로 영향을 주기 때문이다.

자세한 설명은 https://www.acmicpc.net/board/view/35413 질문 글에서 확인할 수 있다.