백준 16920 확장 게임

haruponea·2021년 3월 27일
0

BOJ

목록 보기
29/41

문제 링크https://www.acmicpc.net/problem/16920

풀이
각 플레이어가 움직일 수 있는 칸의 수를 p_move리스트에 저장했습니다. 또한 각 플레이어의 큐를 q리스트에 저장시키고 전체를 돌면서 모든 플레이어의 초기 상태를 초기화 시켰습니다. 여기서 vis리스트는 사용하지 않았는데 board의 .칸을 숫자칸으로 바꾸는 것 자체가 vis를 체크하는 것과 같은 효과를 내기 때문입니다. 그후 bfs함수는 target(player)를 입력받아 bfs-leveling을 사용해서 level이 움직일 수 있는 칸과 같을만큼만 bfs를 돌리도록 했습니다. 즉 한번 돌때마다 현재칸에서 움직일 수 있는 횟수만큼만 움직이도록 하고 다음 player의 bfs를 실행하도록 했습니다. 마지막으로 성의 갯수는 defaultdict를 사용하여 저장했습니다.

Python

from collections import deque, defaultdict
import sys
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
>
n, m, p = map(int, sys.stdin.readline().split())
p_move = list(map(int, sys.stdin.readline().split()))
board = [list(sys.stdin.readline().strip()) for _ in range(n)]
q = [deque() for _ in range(p)]
cnt = defaultdict(int)
for i in range(n):
    for j in range(m):
        if board[i][j] != '.' and board[i][j] != '#':
            q[int(board[i][j]) - 1].append((i, j))
>
def bfs(target):
    move = p_move[target - 1]
    level = 0
    while q[target-1]:
        size = len(q[target-1])
        for _ in range(size):
            x, y = q[target - 1].popleft()
            cnt[target - 1] += 1
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if 0<= nx < n and 0<= ny < m and board[nx][ny] == '.':
                    board[nx][ny] = str(target)
                    q[target - 1].append((nx, ny))
        level += 1
        if move == level:
            return
>
while True:
    remain = False
    for i in q:
        if len(i) != 0:
            remain = True
            break
    if remain:
        for k in range(p):
            bfs(k + 1)
    else:
        print(*cnt.values())
        break

0개의 댓글