백준 16920 확장게임

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

 

​​

BFS 문제다. BFS 문제에서 가장 핵심은 얼마나 방문을 최적화 할 것인지다. 방문을 최적화 하지 못하면 3가지 문제중 하나가 필수적으로 발생한다. 첫번째는 큐에 어마어마하게 많은 것들이 들어가게 되면서 메모리가 터진다. 두번째는 잘못된 방문 체크로 인해 방문한 곳에 계속 방문하며 무한루프에 빠지게 된다. 세번째는 과하게 방문해서 TLE가 발생한다.

​

이 부분을 고려해서 문제를 해결했다

​

​

1. 1. 매 턴마다 플레이어 순서대로 성을 확장한다. (한 플레이어 확장 → 다음 플레이어 확장)→ 따라서 For문을 통한 순서대로의 처리가 필요한 것을 이해할 수 있다.
2. 한번에 확장 가능한 영역은 10억이다. 그런데 N,M이 각각 1000이기 때문에 많아도 1,000,000이라 좌표 압축 같은 것들을 고려하지 않아도 된다.

​위에서 간단한 것들에 대해 먼저 고려했다. 그렇다면 이제 방문을 확인해봐야한다.

1. ​​방문 체크 배열을 매번 만들어야 할까? → No
   • 첫번째 방문했던 곳이 있다면 다시는 방문할 일이 없다. 왜냐하면 이미 그 성으로 확장이 되었고, 그 좌표에는 단 하나의 성만 지어지기 때문이다. 또한 다른 플레이어에 의해 성이 탈환된다는 조건 또한 없다. 따라서 방문 체크 배열은 단 한번만 만들면 된다
2. ​성은 어떻게 확장해야할까?
   • 처음에 확장했던 성은 이후 고려할 필요가 없다. 아래 이미지를 보자. 노란색으로 표시된 1에서 1턴이 지나면 파란색으로 성이 확장된다. 최외곽 성은 항상 내부의 성보다 더 많은 확장이 가능한 것을 보장한다. 따라서, 노란색 성은 다시는 볼 필요가 없다.

결론은 성을 확장할 때, 이번에 큐에 들어갔던 좌표들은 다음에는 넣지 않아도 된다. 오로지, 이번 순번에서 변경점이 발생한 성에 대해서만 다음 순서에서 체크를 해야한다.

 

​

​

import sys
from collections import deque


def sol(n,m,my_map, p_castle, distance, p):

    que = deque()
    stack = []
    fix_count = 0

    while p_castle[p]:
        pr, pc = p_castle[p].pop()
        que.append((pr,pc,0))
        v[pr][pc] = 0

    while que :
        r,c,dis = que.popleft()
        next_dis = dis + 1

        for rr,cc in tra_list:
            next_r, next_c = r + rr, c + cc

            if next_dis > distance:
                break

            # 이 경우에만 뭔가 할 수 있음.
            if -1 < next_r < n and -1 < next_c < m:

                # 한번도 방문한 적이 없고
                if v[next_r][next_c] == 9876543210 and my_map[next_r][next_c] == ".":

                    # 변경점이 발생한 경우
                    if my_map[next_r][next_c] != p:
                        fix_count +=1
                        stack.append((next_r, next_c))
                        que.append((next_r, next_c, next_dis))
                        v[next_r][next_c] = 0


    # 맵에 업데이트
    if fix_count!= 0 :
        answer_castle[p] += fix_count
        while stack :
            r,c = stack.pop()
            my_map[r][c] = p
            p_castle[p].append((r,c))
        return True

    return False



tra_list = [[1,0],[0,1],[-1,0],[0,-1]]


#변수 초기화
n,m,p = map(int,sys.stdin.readline().split())
temp = list(map(int,sys.stdin.readline().split()))
p_list = [0]
for i in temp:
    p_list.append(i)

p_castle = [[] for _ in range(p+1)]
my_map = [[] for _ in range(n)]
for i in range(n):
    ss = str(sys.stdin.readline().rstrip())
    for s in ss:
        if s == "." or s == "#":
            my_map[i].append(s)
        else:
            my_map[i].append(int(s))

v = [[9876543210 for _ in range(m)] for _ in range(n)]
for r in range(n) :
    for c in range(m) :
        if my_map[r][c] != "."  and my_map[r][c] != "#":
            now_castle = my_map[r][c]
            p_castle[now_castle].append((r,c))



# 정답값
answer_castle = [0 for _ in range(p+1)]
for idx in range(len(p_castle)):
    answer_castle[idx] = len(p_castle[idx])


while 1 :

    going_flag = False
    for ppp in range(1, p+1):
        check = sol(n, m, my_map, p_castle, p_list[ppp], ppp)
        if check :
            going_flag = True

    if not going_flag:
        break

print(" ".join(map(str, answer_castle[1:])))