2 minute read

문제

접근 방법

우선 문제 설명대로 각 플레이어마다 확장을 하는 것을 반복하면 된다고 생각했다.

이때 문제점은 다음과 같다.
1) 플레이어가 허용된 거리까지만 확장해야 하는 것

2) 각 플레이어가 이전 턴에서 확장한 성들의 위치를 기억해야 한다는 것

문제 조건에서 메모리 제한이 충분하기 때문에 문제를 간단하게 풀기 위해 메모리에 대한 신경을 쓰지 않았다.

혀용된 거리까지만 확장하게 하기 위해서 queue에 이동한 거리도 포함시켰다. 이때, 그럼 queue에서 허용된 거리의 최대치까지 온 좌표가 pop될 때, 어떻게 할 것인가가 두 번째 문제로 이어진다. $\rightarrow$ 최대치까지 이동한 좌표가 나오기 시작한다는 것은 BFS 특성 상 그 뒤에 queue에 있는 좌표들도 모두 최대치까지 이동한 좌표들이라고 생각했다.

따라서 최대치까지 이동한 좌표가 나오자마자 while 문을 끝냈다.

그러면 queue에 남아있는 좌표들은 어떻게 해야 할까?
$\rightarrow$ queue에 남아있는 값들은 최대치까지 확장된 성들의 위치가 된다. 이로써 두 번째 문제를 해결했다. queue 값들을 player 별로 저장하면 된다

이 사고 과정으로 코드를 구현했다.

이때, 배우게 된 것이 python에서 pointer를 사용하는 것이다. List의 원소가 list라고 할 때 element = list[n]으로 불러오면 element에 복사된 것이 아니라 element는 list를 참조하게 되는 것이다.

queues = [deque() for _ in range(p+1)]에서 각 deque 값을 bfs 할 때마다 update하기 위해 queues[player]에 남은 q로 update했는데 이러면 효율적이지 않다.

처음부터 q = queues[player]을 해서 q가 player의 queue을 지목하게 한 뒤 q를 update하면 된다.

정답 코드

import sys
from collections import deque

input = sys.stdin.readline

'''
각 플레이어마다 확장을 한번 하고 난 뒤의 queue을 저장해놓고 다시 자기의 턴이 되면 그 queue을 그대로 bfs
'''
n,m,p = map(int, input().split())

s = [0] + list(map(int, input().split()))
maps = []

for _ in range(n):
  maps.append(list(input().rstrip()))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

is_placed = [[0]*m for _ in range(n)]

#각 플레이어들의 queue
queues = [deque() for _ in range(p+1)]

#각 플레이어가 확장한 수
placed_nums = [0]*(p+1)

for i in range(n):
  for j in range(m):
    if maps[i][j]!='#' and maps[i][j]!='.':
      queues[int(maps[i][j])].append((i,j,0))
      is_placed[i][j] = int(maps[i][j])
      placed_nums[int(maps[i][j])] += 1

# for place in is_placed:
#   print(place)

# print('=========')
      
'''
expand 만큼 확장하고 끝내기. 남은 지점들은 queue에 저장
확장된 곳은 is_placed에 저장
하나도 확장을 하지 못한다면 0, 확장이 가능하다면 1을 출력
'''

def bfs(player, queue, expand, turn):
  q = deque(queue)
  expanded_once = False
  while q:
    h,w,times = q.popleft()
    #expand 만큼 확장해서 생긴 castle이 존재하게 된다면 끝내기
    if times == expand*turn:
      q.appendleft((h,w,times))
      break
    for dh,dw in moves:
      new_h, new_w = h+dh, w+dw
      #벽이 아니고 빈 곳일 때만 확장이 가능
      if 0<=new_h<n and 0<=new_w<m and (maps[new_h][new_w]=='.' and is_placed[new_h][new_w]==0):
        q.append((new_h, new_w, times+1))
        is_placed[new_h][new_w] = player
        placed_nums[player]+=1
        expanded_once = True
        
  queues[player] = q
  # for place in is_placed:
  #   print(place)
  # print('=========')
  if expanded_once:
    return 1

  else:
    return 0
  
    
        
    
turns = 1 # turn 수
did_expand = 0 # 모든 플레이어들이 확장했는지 확인
expanded = [True]*(p+1) #전 turn에 확장했는지 확인

while True:
  for player in range(1,p+1):
    #전에 확장하지 못했다면 넘기기
    if not expanded[player]:
      continue
    
    result = bfs(player, queues[player], s[player], turns)
    if result == 1:
      did_expand+=1
      expanded[player] = True
    else:
      expanded[player] = False
  
  #확장이 아무도 안 되었다면
  if did_expand == 0:
    break
  #한명이라도 확장이 되었다면
  else:
    turns+=1
    did_expand = 0

print(*placed_nums[1:])

You May Also Enjoy