글 읽기 - 시간 초과 나는 이유를 모르겠어요

postcookie 2년 전 0

안녕하세요?

10026번 문제를 BFS로 풀었는데요.

도대체 어디서 시간 초과가 나는지 모르겠습니다.

너무 궁금해서 다른 코드들도 찾아봤지만 제 코드와 근본적으로 다른 부분은 딱히 없어보입니다. grid를 색약 대상으로 바꾸고 다시 2중 for 루프 도는 것도 다른 코드와 똑같은데 왜 계속 시간 초과를 받는지 이해가 안 됩니다.

도와주시면 감사하겠습니다.

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

dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y, n):
  qu = deque([[x, y]])

  while qu:
    x, y = qu.popleft()
    visited[x][y] = 1
    for l in range(4):
      nx = dx[l] + x
      ny = dy[l] + y
      if 0 <= nx < n and 0 <= ny < n:
        if grid[nx][ny] == grid[x][y] and not visited[nx][ny]:
          qu.append([nx, ny])

def run_grid(n):
  cnt = 0
  for i in range(n):
    for j in range(n):
      if not visited[i][j]:
        bfs(i, j, n)
        cnt += 1
  return cnt


n = int(input())
grid = [list(input()) for _ in range(n)]
visited = [[0 for _ in range(n)] for _ in range(n)]
cnt_1 = run_grid(n)

grid = [['R' if c == 'G' else c for c in row] for row in grid]
visited = [[0 for _ in range(n)] for _ in range(n)]
cnt_2 = run_grid(n)

print(cnt_1, cnt_2)

postcookie 2년 전 2

자문자답입니다.

bfs에서 while문을 검사할 때, visited를 언제 하냐가 문제였습니다.

visited[x][y]를 큐에서 뺄 때 검사하니 여러 번 들어갈 수 있다는 문제였네요.

이 답을 보기 전에 답답해서 dfs로 바꿔서 제출했지만.. ㅎㅎ 저처럼 bfs로 시간 초과나시는 분들이 참고하시기를 바랍니다.

ninykwon19 1년 전 0

덕분에 통과했습니다. 감사합니다^^

battlekjh 1년 전 0

와 감사합니다 ㅋㅋㅋ 이거였네요

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

문제

문제

출처

ICPC

시간 초과 나는 이유를 모르겠어요

postcookie 2년 전 0

postcookie 2년 전 2

ninykwon19 1년 전 0

battlekjh 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말