글 읽기 - 이 두코드의 차이점을 모르겠습니다(정답 포합)

kbiglight 3년 전 0

솔루션1과 솔루션2의 과정 즉, queue를 출럭해서 들어가는 과정을 일일히 다 확인해보았지만

이 1번은 안되고 2번은 정답으로 인정됩니다.

처리과정의 순서를 조금만 바꿔준것이고 연산 횟수의 차이는 없을텐데 왜 이런 차이가 생기는 걸까요?

def solution1(comp):
    queue = deque([comp])
    visited = [False] * (n + 1)
    count = 0
    while queue:
        print(queue)
        target = queue.popleft()
        visited[target] = True
        count += 1
        for new_target in graph[target]:
            if not visited[new_target]:
                queue.append(new_target)

    return count

def solution2(comp):
    queue = deque([comp])
    visited = [False] * (n + 1)
    visited[comp] = True
    count = 1
    while queue:
        print(queue)
        target = queue.popleft()
        for new_target in graph[target]:
            if not visited[new_target]:
                queue.append(new_target)
                visited[new_target] = True
                count += 1

    return count

qera 3년 전 1

위 1번은 큐애서 꺼내고 count를 더하고 2번은 count를 더하며 큐에 추가한다는 차이가 있는데 여기서 1번의 반례는 a-> b, a-> c b->c의 그래프입니다. a체크 후 b,c추가 b에서 c 추가 그 다음 queue에 c가 2개 남게 됩니드. 1번코드는 방문을 체크하지 않기에 c를 중복체크하게 됩니다.

kbiglight 3년 전 1

@qera

감사합니다 어느 부분에서 문제가 생겼는지 파악했습니다!!

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

문제

문제

출처

ICPC

이 두코드의 차이점을 모르겠습니다(정답 포합)

kbiglight 3년 전 0

qera 3년 전 1

kbiglight 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말