글 읽기 - 문제 2665 시간복잡도 계산 어떻게들 하시나요?

chlghksdyd24 1년 전 0

안녕하세요 알고리즘을 잘하고 싶은 초보입니다.

문제를 풀다가 궁금한 점이 있어 질문을 남깁니다.

for문을 사용하여 시간복잡도를 계산하는 방법은 알겠는데 2665번 문제 같이 bfs문제에서 큐를 사용하여 문제를 풀 때 시간 복잡도를 어떻게 따져야 되나요?

큐에 얼마 만큼의 데이터가 삽입될지 대략적으로 알 수 있는 방법이 있나요?

물론 코드에 탐색 대상의 칸(nx,ny)이 현재 있는 칸(x,y)의 방 바꾼 횟수 보다 크면 큐에 삽입하는 조건문을 달았기 때문에 무한 루프를 타지 않을거 라는 걸 알

지만 정확한 시간 복잡도를 따지는 방법이 있는지 궁금해서 글을 올립니다.

답변 주시면 정말 감사하겠습니다.

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

INF = sys.maxsize 

n = int(input())

dx = [0,1,0,-1]  # 행 동서남북 탐색
dy = [1,0,-1,0]  # 열 동서남북 탐색

matrix = []

for i in range(n):
    matrix.append(list(map(int,list(input().strip()))))

qu = deque() # 큐

change_matrix = [[INF]*n for i in range(n)] # 해당칸의 방 색깔 최소 교환 횟수 저장 행렬 (초기값을 무수히 큰 수로 설정)

qu.append((0,0,0))  # x , y , 바꾼 횟수

change_matrix[0][0] = 0 # 시작 칸은 항상 흰방이므로 교환횟수는 0

while(qu):
    x,y,cnt = qu.popleft()
    for i in range(4):  # 동서남북 탐색
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<n and 0<=ny<n:  # 탐색 범위 이내일 경우
            if not matrix[nx][ny] and change_matrix[nx][ny]>cnt+1: # 탐색 칸(nx,ny)이 검은방이고 탐색 칸의 방 색깔 교환횟수가 현재(x,y)칸 방교환 횟수 + 1 보다 클 때
                change_matrix[nx][ny] = cnt + 1 # 탐색 칸의 최소 횟수를 바꾼다. 
                qu.append((nx,ny,cnt+1)) # 큐에 담는다.
            elif matrix[nx][ny] and change_matrix[nx][ny]>cnt:  # 탐색 칸(nx,ny)이 흰방이고 탐색 칸의 방 색깐 교환횟수가 현재(x,y)칸 방교환 횟수 보다 클 때
                change_matrix[nx][ny] = cnt # 탐색 칸의 최소 횟수를 바꾼다.
                qu.append((nx,ny,cnt)) # 큐에 담는다.

print(change_matrix[n-1][n-1]) # 도착칸의 최소 방 교환 횟수 출력