[BOJ] 백준 16920번 확장 게임 (Java)

#16920 확장 게임

난이도 : 골드 2

유형 : 그래프 탐색 / BFS

16920번: 확장 게임

▸ 문제

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

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

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

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

▸ 입력

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

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

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

▸ 출력

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

 

문제 풀이  

턴제로 각 유저들이 움직일 수 있는 거리만큼 성을 차지하는 시뮬레이션을 구현해야 한다. 자료구조 queue와 bfs탐색을 적절하게 사용해주면 된다.

1. input
   1. dis[] 유저가 한 번에 움직일 수 있는 거리를 입력받는다. 
   2. map[][] 게임판 정보를 입력받고 유저가 위치해있으면 해당 정보를 queue에 저장한다.
2. bfs 탐색
   1. user(1 ~ s)를 차례대로 턴이 주어진다.
   2. user마다 각 움직일 수 있는 거리(dis)만큼 움직인다.
      1. dis=1당 user의 현재 위치들에서 상하좌우로 한칸씩 성을 차지한다.
      2. 단 벽이나 누군가의 성이 있는 곳은 차지할 수 없다.
3. 그렇게 모든 탐색이 끝날 때까지 반복문을 돌려주고 최종적으로 각 유저가 갖고있는 성의 개수를 출력한다.

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {

	static class Node{
		int x;
		int y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	static int n, m, s;
	static int[] dis, castles;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static char[][] map;
	static Queue<Node>[] q;
	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());
		s = Integer.parseInt(st.nextToken());
		
		castles = new int[s+1];
		q = new LinkedList[s+1];
		dis = new int[s+1];
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=s; i++) {
			dis[i] = Integer.parseInt(st.nextToken());
			q[i] = new LinkedList<>();
		}
		
		map = new char[n][m];
		for(int i=0; i<n; i++) {
			map[i] = br.readLine().toCharArray();
			for(int j=0; j<m; j++) {
				if('1' <= map[i][j] && map[i][j] <= '9') {
					int userNo = map[i][j]-'0';
					q[userNo].add(new Node(j,i));
					castles[userNo]++;
				}
			}
		}
		bfs();
		for(int i=1; i<=s; i++) {
			System.out.print(castles[i]+" ");
		}
		System.out.println();
	}
	
	static void bfs() {
		while(true) {
			for(int u=1; u<=s; u++) {
				int s_dis = dis[u];
				for(int i=0; i<s_dis; i++) {
					int size = q[u].size();
					for(int j=0; j<size; j++) {
						Node cur = q[u].poll();
						int cx = cur.x;
						int cy = cur.y;
						for(int d=0; d<4; d++) {
							int nx = cx +dx[d];
							int ny = cy +dy[d];
							if(nx < 0 || ny < 0 || nx > m-1 || ny > n-1) continue;
							if(map[ny][nx] == '.') {
								map[ny][nx] = (char) (u+'0');
								q[u].add(new Node(nx, ny));
								castles[u]++;
							}
						}
					}
					if(q[u].isEmpty()) break;
				}
			}
			boolean f = true;
			for(int u=1; u<=s; u++) {
				if(!q[u].isEmpty()) {
					f = false;
					break;
				}
			}
			if(f) break;
		}		
	}
}