글 읽기 - 시간초과가 왜 일어나는지 도저히 모르겠습니다.

justy 1년 전 0

시간 복잡도는 충분히 남는 것 같은데 이유를 모르겠습니다. 살려주세요 ㅠㅠ

import sys
import copy
from collections import deque
n, m = map(int, sys.stdin.readline().split())
graph = []
for _ in range(n):
  graph.append(list(map(int, sys.stdin.readline().rstrip())))
  
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def BFS(area_graph, x, y, group):
  count = 1
  q = deque()
  q.append((x, y))
  area_graph[x][y] = group
  while q:
    x, y = q.popleft()
    for d in range(4):
      nx = x + dx[d]
      ny = y + dy[d]
      if 0 <= nx < n and 0 <= ny < m:
        if area_graph[nx][ny] == 0:
          area_graph[nx][ny] = group
          q.append((nx, ny))
          count += 1
  return count
          
# 영역을 구한다.
area = []
group = 2
area_graph = copy.deepcopy(graph)
for i in range(n):
  for j in range(m):
    if area_graph[i][j] == 0:
      count = BFS(area_graph, i, j, group)
      area.append(count)
      group += 1

def get_count(x, y):
  count = 0
  visited_area = [False] * (len(area) + 2)
  for d in range(4):
    nx = x + dx[d]
    ny = y + dy[d]
    if 0 <= nx < n and 0 <= ny < m:
      group = area_graph[nx][ny]
      if area_graph[nx][ny] >= 2 and visited_area[group] == False:
        count += area[group - 2]
        visited_area[group] = True
  return count
        
      
# 전체 지도를 탐색한다.
for i in range(n):
  for j in range(m):
    if graph[i][j] == 1:
      graph[i][j] = (get_count(i, j) + 1) % 10

for i in range(n):
  for j in range(m):
    print(graph[i][j], end='')
  print()

cinador 1년 전 0

42번째 줄에 벽 하나마다 visited 배열을 만들어주는 데에서 시간초과가 발생하는 것으로 보입니다.

최악의 경우를 생각해보면 홀수줄에는 1010... 짝수줄에는 0101... 이 1000*1000에서 반복된다고 가정하면 area에는 50만개의 원소가 들어있고, 벽은 50만개 존재합니다.

이 경우에 벽 하나마다 원소가 50만개인 리스트를 작성해야 되니 시간초과가 발생합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과가 왜 일어나는지 도저히 모르겠습니다.

justy 1년 전 0

cinador 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말