글 읽기 - 시작점을 방문처리하지 않았는데 통과한 이유가 궁금합니다.

pumpkin 2년 전 0

안녕하세요.

dfs를 최초 호출할 때 방문처리를 하지 않고 depth를 0부터 시작해서 종료조건을 5로 설정했을 때는 정답을 받았습니다.

하지만 depth를 1부터 시작하니 dfs를 최초 호출할 때 방문처리를 하지 않으니까 틀렸습니다로 나오네요.

왠지 첫 번째 답에서 오답인 케이스가 존재할 것 같은데 통과한 이유가 무엇일까요?

두 소스 모두 첨부합니다!

// 첫 번째 코드

N = 0
M = 0
friend_list = [[] for _ in range(2005)]
visited = [False] * 2005
answer = 0


def dfs(current, depth):
    global answer
    if answer == 1:
        return
    elif depth == 5:
        answer = 1
        return

    for friend in friend_list[current]:
        if visited[friend] is False:
            visited[friend] = True
            dfs(friend, depth + 1)
            visited[friend] = False


N, M = map(int, input().split())


for i in range(M):
    a, b = map(int, input().split())
    friend_list[a].append(b)
    friend_list[b].append(a)

for i in range(N):
    // 이 부분에서 의문이 있습니다.
    dfs(i, 0)

print(answer)

//////////////////////////////////////////////////////////////
// 두 번째 코드
N = 0
M = 0
friend_list = [[] for _ in range(2005)]
visited = [False] * 2005
answer = 0

def dfs(current, depth):
    global answer
    if answer == 1:
        return
    elif depth == 4:
        answer = 1
        return

    for friend in friend_list[current]:
        if visited[friend] is False:
            visited[friend] = True
            dfs(friend, depth + 1)
            visited[friend] = False


N, M = map(int, input().split())


for i in range(M):
    a, b = map(int, input().split())
    friend_list[a].append(b)
    friend_list[b].append(a)

for i in range(N):
    visited[i] = True
    dfs(i, 0)
    visited[i] = False

print(answer)

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

문제

문제

출처

ICPC

시작점을 방문처리하지 않았는데 통과한 이유가 궁금합니다.

pumpkin 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말