Dot Algo∙ DS/PS

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

루지 2022. 3. 19. 18:09

    #16920 확장 게임

    난이도 : 골드 2

    유형 : 그래프 탐색 / BFS

     

    16920번: 확장 게임

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

    www.acmicpc.net

    ▸ 문제

    구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 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;
    		}		
    	}
    }