글 읽기 - DFS 정상 BFS 시간초과 질문

codren 2년 전 1

문제 푸는 원리는 R G B RG 를 각각 수행해서 count를 세는 방식입니다.

이때 R G 이면 vistit 으로 설정 하지않고 RG로 설정하여 마지막에 RG도 count 할 수 있게 했습니다.

DFS로 하면 120ms 정도로 성공하는데

같은 원리로 BFS를 수행하면 답은 제대로 나오지만 시간초과가 발생합니다.

어느부분에서 어떤 차이로 인해서 시간초과가 발생하는지 혹시 알 수 있을까요??

######################### DFS 부분 ########################
import sys
sys.setrecursionlimit(100000)
def dfs(x,y,color):
    if x < 0 or  x > n-1 or y < 0 or y > n-1:
        return False

    if picture[x][y] == color:
        if picture[x][y] == 'R' or picture[x][y] =='G':
            picture[x][y] = 'RG'
        else:
            picture[x][y] = 'v'
        dfs(x-1,y,color)
        dfs(x+1,y,color)
        dfs(x,y-1,color)
        dfs(x,y+1,color)

        return True
    else:
        return False

n = int(sys.stdin.readline())
picture = []
count = []

for _ in range(n):
    picture.append(list(sys.stdin.readline().rstrip()))


for color in ['R','G','B','RG']:
    temp = 0

    for i in range(n):
        for j in range(n):

            if dfs(i,j,color) == True:
                temp += 1

    count.append(temp)

print(sum(count[:3]), sum(count[2:]))


############################## BFS 부분 ############################ 

import sys
from collections import deque

def bfs(x,y,color):

    queue = deque()
    queue.append((x,y))
    
    if picture[x][y] == color:
        while(queue):
            x,y = queue.popleft()
            if color == 'R' or color == 'G':
                picture[x][y] = 'RG'
            else:
                picture[x][y] = 'v'

            for i in range(4): 
                nx = x + dx[i]
                ny = y + dy[i] 

                if nx < 0 or nx > n-1 or ny < 0 or ny > n-1:
                    continue
                
                if picture[nx][ny] == color:
                    queue.append((nx,ny))
    else:
        return False
   
    return True 
            
n = int(sys.stdin.readline())

dx = [-1,1,0,0]
dy = [0,0,-1,1]
count = []
picture = []

for _ in range(n):
    picture.append(list(sys.stdin.readline().rstrip()))

for color in ['R','G','B','RG']:
    temp = 0

    for i in range(n):
        for j in range(n):
            if bfs(i, j,color) == True:
                temp += 1
    
    count.append(temp)

print(sum(count[:3]), sum(count[2:]))

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

문제

문제

출처

ICPC

DFS 정상 BFS 시간초과 질문

codren 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말