글 읽기 - DFS로 풀어봤는데 어디가 틀린지 궁금합니다.

won64312000 2년 전 0

BFS, 플로이드-와샬로 풀어보고 DFS로 풀어보고 싶어서 풀어봣는데 계속 틀려서 질문 드립니다.

각 점들마다 DFS를 시작해서 그 값을 visited에 저장했습니다.

dfs를 하는 과정에서 visited에 저장되는 값인 cnt가 7이 되면 거리가 7칸이기 때문에 그자리에서 바로 return을 시켜줌으로써 분기점을 정했습니다.

#DFS 이용

import sys

N, K = map(int, sys.stdin.readline().split())
graph = [[] * (N+1) for i in range(N+1)]
check = 0
for _ in range(K):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
#print(graph)
def dfs(x,cnt,before):
    if cnt == 7:
        return

    visited[x] = visited[before] + 1
    #print(visited)
    for nx in graph[x]:
        if visited[nx] == -1:
            dfs(nx,cnt+1,x)


for i in range(1, N+1):
    visited = [-1] * (N + 1)
    dfs(i, 0, 0)
    #print('*********')
    if max(visited) > 6 or -1 in visited[1:]:
        check = 1
        break

if not check:
    print('Small World!')
else:
    print('Big World!')

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

문제

문제

출처

ICPC

DFS로 풀어봤는데 어디가 틀린지 궁금합니다.

won64312000 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말