글 읽기 - 시간초과 되어야 하는 제 코드가 왜 통과하는지 모르겠습니다.

rlarudgh2017 1년 전 0

혹시 몰라서 코드도 같이 올렸는데 일단 밑에 시간복잡도 계산하는것만 봐주세요.

저는 BFS함수로 dirty tiles와 시작점을 포함한 노드들 각각의 거리를 모두 구하고 dirty tiles의 순서를 dfs로 만든 permutation 함수로 구했습니다. DFS함수로 순서가 한 번 정해질 때마다 BFS함수로 미리 구해놓았던 거리를 이용해서 거리의 합을 구한 뒤 min함수로 그중 최소를 구하는 형식입니다.

BFS 시간복잡도를 검색해보니, O(v + e)라고 되어있고 permutation할 때 O(n!)이니 총 시간복잡도가 n! * (v + e)입니다.

최대로 입력이 들어올 경우 dirty tiles의 개수가 10개이고 정점의 개수는 400개, 간선의 개수는 대략 400 * 4 정도 될테니 10! * 2000 = 7,257,600,000 입니다.

보통 1초를 10^8로 잡는다고 알고 있는데 제가 잘못알고 있는건지 아니면 시간복잡도 계산을 잘못한건지 모르겠습니다. 위의 설명에서 어느부분이 잘못되었나요?

import sys
from collections import deque
input = sys.stdin.readline
INF = 10 ** 9
dy = [0, 0, -1, 1]
dx = [-1, 1, 0, 0]

def dfs(depth = 1):
    global v, ans
    if depth >= v:
        cost = 0
        for i in range(v - 1):
            cost += edges[nodes[order[i]][0]][nodes[order[i]][1]][nodes[order[i + 1]][0]][nodes[order[i + 1]][1]]
        ans = min(ans, cost)
        return
    for i in range(1, v):
        if visited[i]:
            continue
        order.append(i)
        visited[i] = True
        dfs(depth + 1)
        order.pop()
        visited[i] = False
        
def inRange(y, x):
    if 0 <= y < h and 0 <= x < w:
        return True
    return False

def bfs(start):
    q = deque([start])
    distance[start[0]][start[1]] = 0
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if not inRange(ny, nx) or floor[ny][nx] == 1 or distance[ny][nx] <= distance[y][x] + 1:
                continue
            q.append((ny, nx))
            distance[ny][nx] = distance[y][x] + 1

while True:
    w, h = map(int, input().split())
    if (w, h) == (0, 0):
        exit(0)
    floor = [[0] * w for _ in range(h)]
    nodes = deque()
    edges = [[[[0] * 20 for _ in range(20)] for _ in range(20)] for _ in range(20)]
    for i in range(h):
        tmp = input()
        for j in range(w):
            if tmp[j] == 'o':
                nodes.appendleft((i, j))
            elif tmp[j] == '*':
                nodes.append((i, j))
            elif tmp[j] == 'x':
                floor[i][j] = 1

    v = len(nodes)
    for node in nodes:
        distance = [[INF] * w for _ in range(h)]
        bfs(node)
        for otherNode in nodes:
            if node == otherNode:
                continue
            edges[node[0]][node[1]][otherNode[0]][otherNode[1]] = distance[otherNode[0]][otherNode[1]]

    ans = INF
    order = deque([0])
    visited = [False] * v
    visited[0] = True
    dfs()
    if ans >= INF:
        ans = -1
    print(ans)

cinador 1년 전 0

dfs 도중에 bfs를 진행한 것이 아니라 bfs를 진행한 후에 dfs를 진행한거 아닌가요??

dfs가 종점에 도달한 경우마다 bfs를 돌렸으면 모를까 이미 bfs로 나온 결과값을 이용한 거니까 시간복잡도를 곱하는게 아니라 더해야 할거 같습니다.

rlarudgh2017 1년 전 0

헐 감사합니다

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