(백준16932&Python) BFS/DFS 솔루션에서 타임아웃 발생시 전처리 방법이 있는지 고려

# 문제

백준 16932 Shape Making Python Solution

# 코드

## 성공적인 솔루션

import sys
from collections import deque

N,M = map(int, sys.stdin.readline().split())

board = list()
for _ in range(N) :
  line = list(map(int,sys.stdin.readline().split()))
  board.append(line)

dirs = (
  (-1,0), (0,1), (1,0), (0,-1)
  )


# 1 모양들 부분집합들의 크기를 미리 구해서 memo에 추가해놓는다
# 위치기록용 스택을 활용한다.
# 0에서 돌려서 memo를 활용한다
memo = ( (-1) * M for _ in range(N))
number = 0
for row in range(N) :
  for col in range(M) :
    if board(row)(col) == 1 and memo(row)(col) == -1 : # 한번도 들린곳이 아니기 때문에 루틴을 수행한다.
      cnt = 1
      cur = (row, col)
      stk = deque()
      dq = deque()
      dq.append(cur)
      stk.append(cur)
      memo(row)(col) = True

      while len(dq) != 0:
        now_cur = dq.popleft()

        for dir in dirs :
          next = (now_cur(0) + dir(0), now_cur(1) + dir(1))
          if 0 <= next(0) < N and 0<= next(1) < M : # 범위 안에 있고
            if memo(next(0))(next(1)) != True and board(next(0))(next(1)) == 1: # 방문했던 곳이 아니라면
              cnt +=1
              dq.append(next)
              stk.append(next)
              memo(next(0))(next(1)) = True

      while len(stk) != 0:
        now_cur = stk.pop()
        memo(now_cur(0))(now_cur(1)) = (cnt,number)
      number+=1
# print(memo)

mmax = 0
for row in range(N) :
  for col in range(M) :
    if board(row)(col) == 0 :
      candidate = set()
      sum = 1
      for dir in dirs : # 4방향 돌려
        next = (row + dir(0), col + dir(1))

        if 0 <= next(0) < N and 0<= next(1) < M : # 범위 안이면
          if memo(next(0))(next(1)) != -1 :
            poped = memo(next(0))(next(1))
            if poped(1) not in candidate : # 포함되지 않았으면
              candidate.add(poped(1))
              sum+=poped(0)
      mmax = max(mmax,sum)

print(mmax)

## 해결 실패(시간 초과)

###--- BFS를 이용하는 풀이 시간초과 ---###
mmax = 0
# 0인곳에서 시작해서, 0의 모양을 1로 바꾸고, 최대값을 구한다.
for row in range(N) :
  for col in range(M) :
    if board(row)(col) == 0 :
      visit = ( (False) * M for _ in range(N))

      dq = deque()
      dq.append((row,col))
      visit(row)(col) = True

      cnt = 1
      while len(dq) != 0 :
        cur = dq.popleft()

        for dir in dirs :
          next = (cur(0) + dir(0), cur(1) + dir(1))
          if 0<= next(0) < N and 0<= next(1) < M : # 범위 안이라면
            if visit(next(0))(next(1)) == False and board(next(0))(next(1)) == 1: # 방문하지 않았다면
              dq.append(next) # 큐어 넣어주기
              visit(next(0))(next(1)) = True # 방문처리
              cnt +=1

      mmax = max(mmax,cnt)

print(mmax)

# 해결하다

• 루프 문이 시간 초과된 시작점으로 모든 0점을 1로 변경하여 최대 크기를 찾는 솔루션인 시간 초과에 유의하십시오.
• 이를 해결하기 위해 도형을 그룹으로 나누고 그룹의 크기와 개수를 지정했습니다. 이러한 전처리 과정을 거친 후 0점부터 4방향 탐색을 통해 다른 그룹의 크기 합을 구하여 최대값을 찾는 문제로 접근하였다.
• 그룹화 프로세스가 스택을 사용하는 메모 배열로 업데이트되었습니다. 그룹 크기와 그룹 번호가 여기에 포함됩니다.
• 스택을 사용하지 않고 그룹의 개수만 넘버링하고 그룹의 크기만 따로 저장하면 시간을 더 단축할 수 있을 것 같다.
• 여하튼 이 문제를 풀려고 한 이유는 timeout -> DP를 사용할 수 있는지 알아보고, DP를 적용할 방법을 찾던 중 위의 전처리 방법을 찾았습니다.
• 또한 Python 집합은 O(1) 속도로 찾을 수 있으므로 사용하고 싶습니다.
  • 만약에 찾을 번호 안에 없다 세트