[백준 16920] 확장 게임 해설 및 풀이 (파이썬)

구현이 좀 빡센 BFS 문제였다.

테스트케이스에 n, m, p가 주어진다.

n,m은 게임판의 사이즈, p는 플레이 하는 인원의 수다.

 

그후에 S₁, S₂, ...S_p가 주어진다.

각 플레이어의 한턴에 움직일 수 있는 거리다.

 

그후에 게임판이 주어진다.

 

예시) 테스트케이스 7번

1..1
#.##
....
...2

'숫자'는 플레이어의 인덱스이고,

. 은 갈 수 있는 길,

#은 벽을 의미한다.

 

 

구현이 그리 어렵진 않았지만, 헛도는 것을 예외 처리 하는게 중요하다.

 

코드 1

import sys
from collections import deque
input = sys.stdin.readline

n,m,p = map(int,input().split())
castle = [[] for _ in range(p+1)]
power = [0]+list(map(int,input().split()))
graph = [list(input().rstrip()) for _ in range(n)]
cnt = [0]*(p+1)

for i in range(n):
    for j in range(m):
        if graph[i][j] != '.' and graph[i][j] != '#':
            cnt[int(graph[i][j])] += 1
            castle[int(graph[i][j])].append((i,j))



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


def bfs():
    while 1:
        flag = False
        for i in range(1,p+1): # 
            if len(castle[i]) > 0:
                flag = True
                break
        if flag == False:
            break
        for i in range(1,p+1):
            for _ in range(power[i]):
                q = deque(castle[i])
                castle[i].clear()
                while q:
                    x,y = q.popleft()
                    for movex,movey in moves:
                        nx = x + movex
                        ny = y + movey
                        if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == '.':
                            graph[nx][ny] = str(i)
                            castle[i].append((nx,ny))
                            cnt[i] += 1
        
bfs()
print(*cnt[1:])

각 플레이어 인덱스마다 다음에 이동할 곳을 castle이라는 2차원 배열에 넣고,

모든 castle이 비어있다면, 연산이 끝난것으로 판단하고 cnt에서 세어준 것을 출력한다.

 

결과 : ⌛ 시간 초과

 

 

코드 2, 3

import sys
from collections import deque
input = sys.stdin.readline

n,m,p = map(int,input().split())
castle = [deque() for _ in range(p+1)]
power = [0]+list(map(int,input().split()))
graph = [list(input().rstrip()) for _ in range(n)]
cnt = [0]*(p+1)


for i in range(n):
    for j in range(m):
        if graph[i][j] != '.' and graph[i][j] != '#':
            cnt[int(graph[i][j])] += 1
            castle[int(graph[i][j])].append((i,j))



moves = [(0,1),(1,0),(0,-1),(-1,0)]
def bfs():
    is_moved = True
    while is_moved:
        is_moved = False
        for i in range(1,p+1):
            q = castle[i]
            for _ in range(power[i]):
                for _ in range(len(q)):
                    x,y = q.popleft()
                    for movex,movey in moves:
                        nx = x + movex
                        ny = y + movey
                        if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == '.':
                            graph[nx][ny] = str(i)
                            q.append((nx,ny))
                            cnt[i] += 1
                            is_moved = True
        
bfs()
print(*cnt[1:])

castle을 2차원 데큐로 바꿨다.

castle = [[] for _ in range(p+1)]에서
castle = [deque() for _ in range(p+1)] 으로 바꿧다.

얕은 복사 로직을 이용하려고 데큐로 저장한 후에 BFS코드 내에서는 q = castle[i]로 복사해서 연산 시작한다.

이렇게 되면 매번 q를 초기화 하지 않고 처리할 수 있어서 시간단축에 도움된다.

 

그리고 is_moved 변수를 만들어서 새로운 성 건설이 진행되었는지 확인한다.

한번도 건설을 하지 않았다면 종료한다.

 

결과 : ⌛ 시간 초과

 

이렇게까지 했는데 시간초과가 나길래 질문을 해서 겨우 풀었다.

틀린 이유는 매번 비어있는 castle[i]까지 전부 계산을 해줬기 때문이다.

예를 들자면

1...
###.
....
.###
..#2

이런 식의 게임판이 있다면, 2의 큐는 처음부터 끝까지 비어있다.

하지만 모든 플레이어의 큐를 전부 입력받아서 처리하게 구현했기 때문에, 불필요한 연산이 추가되기에 시간 초과가 났던 것이다.

위 경우에는 1이 한번 이동할 때마다 2의 모든 경우를 확인을 해준다.

 

이에 대해 예외 처리 코드 2줄을 추가하니까 널널하게 정답처리가 됐다.

import sys
from collections import deque
input = sys.stdin.readline

n,m,p = map(int,input().split())
castle = [deque() for _ in range(p+1)]
power = [0]+list(map(int,input().split()))
graph = [list(input().rstrip()) for _ in range(n)]
cnt = [0]*(p+1)


for i in range(n):
    for j in range(m):
        if graph[i][j] != '.' and graph[i][j] != '#':
            cnt[int(graph[i][j])] += 1
            castle[int(graph[i][j])].append((i,j))



moves = [(0,1),(1,0),(0,-1),(-1,0)]
def bfs():
    is_moved = True
    while is_moved:
        is_moved = False
        for i in range(1,p+1):
            if not castle[i]: # 비어있다면 continue
                continue
            q = castle[i]
            for _ in range(power[i]):
                if not q: # power 연산 중에 비어졌다면 break
                    break
                for _ in range(len(q)):
                    x,y = q.popleft()
                    for movex,movey in moves:
                        nx = x + movex
                        ny = y + movey
                        if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == '.':
                            graph[nx][ny] = str(i)
                            q.append((nx,ny))
                            cnt[i] += 1
                            is_moved = True

        
bfs()
print(*cnt[1:])

 

끝!