문제 16920. 확장 게임(BFS 25번)

문제 링크

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

16920번: 확장 게임

 

난이도: 골드 2

 

 

문제 요약 설명

 

플레이어들이 N X M인 격자판 위에서 확장게임을 한다.

확장게임이란 각 플레이어가 순서대로 본인의 모든 성들에서 Si번 상하좌우로 이동하여 이동한 칸에 성을 추가로 짓는 게임이다. 확장게임은 모든 플레이어가 더 이상 확장을 할 수 없을 때 게임이 끝난다. 

격자판이 주어졌을 때, 확장게임이 끝나고 각 플레이어가 가진 성들의 개수를 출력하는 프로그램을 구하시오.

(단, 한 칸에 하나의 성만 존재할 수 있으며, 한 번 성이 지어진 칸은 다른 성이 지어질 수 없다. 또한, 격자판 위에는 참가한 플레이어들의 성들만 존재하며, 모든 플레이어가 하나 이상의 성들을 가진 채로 시작한다.)

입력

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

둘째 줄에 각 플레이어의 이동 횟수 S1, S2, ...SP가 주어진다.

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

 

입력 제한

• 1 ≤ N, M ≤ 1,000
• 1 ≤ P ≤ 9
• 1 ≤ Si ≤ 10^9

입력 예제

// input
3 3 2
1 1
1..
...
..2

// ans
6 3

 

풀이 방식

 

상하좌우로 반복적인 이동을 한다는 점에서 bfs방식으로 문제를 풀면 된다는 걸 알 수 있다. 다만, 조금 주목해야 할 부분이 있다.  주목해야 할 점은 다음과 같다.

각 플레이어는 서로 다른 이동 횟수를 가질 수 있다.

 

보통 bfs문제들은 한 턴에 한 번의 이동 횟수를 가지지만, 해당 문제에서는 어느 플레이어인지에 따라 다른 이동 횟수를 가질 수 있다. 이런 특성때문에 각 플레이어의 이동 가능 횟수에 따른 추가적인 조치를 취해야 한다. 따라서, 다음 턴에 확장할 성의 위치들을 저장한 queue를 플레이어 별로 따로 관리한다. 해당 방법은 플레이어가 최대 9명으로 제한 되기에 적절한 방법이 될 수 있다. 이해를 위한 코드는 다음과 같다.

// pos_list: 플레이어가 다음 턴에 사용할 성의 위치를 저장한 리스트
// player_data_list: 플레이어들의 pos_list를 모은 리스트
// q: 현재 플레이어의 pos_list
queue<pos_data>* q = &player_data_list[player_No].pos_list;

int curr_moveN = 0;     
// 더이상 이동할 수 있는 성이 없거나, 이동 횟수를 초과하는 이동이라면 while문을 나온다.
while(!q->empty() && curr_moveN < player_data_list[player_No].moveN){
    int curr_q_size = q->size();

    // curr_moveN 만큼 이동한 성들의 확장
    for(int i = 0; i < curr_q_size; i++){
       ...
    }
    curr_moveN++;

    // 더이상 확장을 할 수 없을때 확장 게임 자체를 종료한다.
    if(left_space <= 0) return;
}

이렇게 다음 턴에 확장할 성의 위치들을 따로 관리하게 되면 서로 다른 이동 횟수를 가지고 있어도 대응하는 queue에 적용하면 되기 때문에 수월히 진행할 수 있다.

정답 코드 링크

추후 업데이트

참고

해당 문제는 잘못된 조건을 가진다는 이유로 점수를 주지 않는 문제이다. 점수가 목적이라면 해당 문제는 풀지 않는 것이 좋다.