글 읽기 - 어느 부분이 틀렸는지 모르겠습니다

cndqjacndqja 3년 전 0

제출한 코드가 90프로 쯤에서 틀렸다고 나옵니다.

다른 블로그에 나온 코드와 차이를 보니, visited에 거리를 계산하는 차이가 있었습니다.

전 q에 탐색 중인 노드와 해당 노드까지의 거리를 삽입하며 거리를 계산하였습니다.

거리를 구하는 방식에서 차이가 있었으니, 이 부분에 문제가 있을까 싶은데 아직까지 어떤 부분이 문제인지 모르겠습니다.

from _collections import deque

n, m, k, x = map(int, input().split())
data = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    data[a].append(b)


def bfs(start):
    q = deque()
    q.append((start, 0))
    visited = [False for _ in range(n+1)]
    result = []

    while q:
        pop_data, pop_cnt = q.popleft()
        if pop_cnt == k:
            result.append(pop_data)
        if pop_cnt < k:
            for i in data[pop_data]:
                if not visited[i]:
                    q.append((i, pop_cnt+1))
                    visited[i] = True
    return result


def solved():
    result = bfs(x)
    result.sort()
    if len(result) == 0:
        print(-1)
    else:
        for i in result:
            print(i)
solved()

cndqjacndqja 3년 전 0

위 코드에 bfs() 부분을

def bfs(start):
    q = deque()
    q.append(start)
    visited = [-1 for _ in range(n+1)]
    visited[start] += 1
    result = []

    while q:
        pop_data = q.popleft()
        if visited[pop_data] == k:
            result.append(pop_data)
        if visited[pop_data] < k:
            for i in data[pop_data]:
                if visited[i] == -1:
                    q.append(i)
                    visited[i] = visited[pop_data] + 1
    return result

이렇게 바꾸었더니 정답이 나왔습니다.

원래 코드는 왜 안되는지 잘 모르겠습니다...

어떤 반례가 있을까요 ㅠ

djm03178 3년 전 0

질문의 코드에서도 수정한 코드에서 visited[start] += 1을 한 것과 같이 시작점을 visited[start] = True로 방문 체크 해주고 시작하면 됩니다.

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

문제

문제

출처

ICPC

어느 부분이 틀렸는지 모르겠습니다

cndqjacndqja 3년 전 0

cndqjacndqja 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말