글 읽기 - 파이썬 테스트 케이스 정답 . 어디서 틀렸는지 모르겠습니다.

jsch678 1년 전 0

반례나 어디서 틀렸는지 알고싶습니다 ㅠㅠ

from collections import deque
import sys
n,m,k,x = map(int,sys.stdin.readline().split())

visited = [False] * (n+1)

graph = [[]]
minimum_cost= [[]]

for i in range(n):
    graph.append([])
for i in range(m):
    minimum_cost.append([])
    s,t = map(int,sys.stdin.readline().split())
    graph[s].append(t)

# print(graph)
#
cnt = 0
def bfs(graph,start,visited,minimum_cost,val):
    global cnt
    visited[start]=True
    queue = deque([start])
    while queue:
        v = queue.popleft()
        cnt +=1
        # print(v,end=" ")
        for i in graph[v]:
            # print(v, " all i is ",i)
            if not visited[i]:
                # print( "now i : ",i , " now cnt : ",cnt)
                queue.append(i)
                minimum_cost[cnt].append(i)
                visited[i]=True
    arr_ = []
            
    if minimum_cost[val] ==[]:
        print(-1)
    else :
        for i in minimum_cost[val]:
            arr_.append(i)
        arr_.sort()
        for j in range(len(arr_)):
            print(arr_[j])

    
#cnt가 최단거리로 파악가능함.

bfs(graph,x,visited,minimum_cost,k)

adung7 1년 전 2

반례)

5 4 2 1
1 2
1 3
2 4
3 5

답 :

4
5

jsch678 1년 전 0

감사합니다..! 혹시 어디서 틀렸는지 알 수 있을까요..?!

jsch678 1년 전 0

cnt 증가 시키는 타이밍이 문제인것 같네요 해결해보겠습니다. 반례 감사합니다!

adung7 1년 전 1

26번째줄에서 큐에서 원소를 뺄때마다 거리를 표시하기 위한 cnt를 하나 증가시키셨는데

이는 시작 노드로부터의 거리가 제대로 표시되지 않습니다.

위를 예시로 들어 설명해드리자면 1번에서 시작해 2,3을 큐에 넣은 시점에선 cnt가 1이 되겠죠.

여기까진 제대로 작동하는것처럼 보이나 2번을 큐에 꺼내고 cnt증가후 4랑 연결되있으므로 4를 큐에 넣고 다시 큐에 있던 3을 뺄때 cnt가 증가하게 됩니다.(큐에서 원소를 뺄때마다 cnt가 증가되기 때문에)

이로 인해 1->3->5로 가는 거리가 2임에도 불구하고 cnt는 3이 되어 거리가 3으로 표시됩니다. 이로 인해 작성자님 코드에선 4밖에 출력이 안 되는것입니다.

최대한 쉽게 설명하려고 했으나 이해 안 되면 다시 질문주세요.

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

문제

문제

출처

ICPC

파이썬 테스트 케이스 정답 . 어디서 틀렸는지 모르겠습니다.

jsch678 1년 전 0

adung7 1년 전 2

jsch678 1년 전 0

jsch678 1년 전 0

adung7 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말