글 읽기 - 1389 DFS 풀이 무엇이 잘못되었나요 ? ㅠㅠ

heayun126 1년 전 0

문제 보고 BFS가 먼저 떠오르지 않고, DFS가 떠올랐는데 영 깔끔하게 해결되지 않네요..

이 반례는 통과했습니다 !

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

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
def dfs(v, target, count, l):
    if v == target:
        l.append(count)
    elif v != target and visited[v] == False:
        visited[v] = True
        count += 1
        for x in graph[v]:
            dfs(x, target, count, l)
T = [x for x in range(1, N+1)]
L_T = []
for i in range(1, N+1):
    T_N = [x for x in range(1,N+1)]
    T_N.remove(i)
    l_ = []
    for target in T_N:
        visited = [False]*(N+1)
        l = []
        dfs(i, target, 0, l)
        l_.append(min(l))
    L_T.append(sum(l_))
L_T.index(min(L_T)) + 1

sinusoid500 1년 전 0

DFS로 최소경로를 탐색하는 경우 먼저 탐색한 노드가 최소 경로에 해당한다는 보장이 없기 때문에 11번째 줄과 같이 방문 처리를 해주신 경우 문제가 될 것 같습니다.

예를 들어 DFS로 인해 경로 A를 먼저 탐색하고 경로 B를 탐색하는 순서가 되는 경우, 실제 경로는 B가 A보다 짧더라도 먼저 탐색한 A 경로로 인해 경로 B와 중복되는 노드가

방문 처리 되어 경로 B에 대한 탐색이 안 되지 않을까 싶습니다.

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

문제

문제

출처

ICPC

1389 DFS 풀이 무엇이 잘못되었나요 ? ㅠㅠ

heayun126 1년 전 0

sinusoid500 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말