특정거리의 도시 (bfs/dfs)

어려운 문제는 아니지만 큐에 스타트를 넣고 진행하는 코드와 스타트 다음부터 시작하는 코드의 정오답 차이가 나서 이유를 한참 찾았습니다.

 

 

아직도 이유를 잘 몰라서 질문 게시판에 글을 올려놨는데 k가 0인것도 아닌데 어디서 오답이 나는 건지 너무 궁금하네요..

->> 문제를 해결했습니다. 고민 결과 밑에 큐에 넣은 부분과 다른 부분이 어딘가 곰곰히 생각해봤더니, visited 부분을

append 할때 체크를 안한다는 점 같은 게 있었습니다.

 

해당 부분을 수정해 append 시 visited[i]!=1 일때를 조건으로 추가해주고 방문한 것도 visited처리를 해주면 올바르게 정답으로 출력됩니다.

 

이유가 뭘까 고민을 해봤더니, 그래프 그림과 다르게 생각해보면 1,2 1,2 이런 식으로 단방향 그래프는 맞지만 동일한 도로가 여러개 있을 수 있다는 생각이 들었습니다.

 

따라서 visited를 체크 안하고 처음에 append를 하게 되면 다음에 경로가 1인 도로들이 중복으로 추가 될 수 있고, 이는 추후 거리를 계산하는데 같은 노드를 여러번 처리할 수도 있게됩니다. (그런데 거리가 달라지지는 않을 것 같은데...) ->(추가확인)

 

아래 코드에서 주석부분을 변경하면 오답이 됩니다 -> 밑에 변경 코드를 추가했습니다.

from collections import deque

 

n, m, k, x = map(int, input().split())

 

board = [[] for _ in range(n+1)]

visited = [0] * (n+1)

 

for i in range(m):

    a , b = map(int,input().split())

    board[a].append(b)

 

q = deque()

 

q.append((x,0)) #해당 코드대신 밑 주석 부분을 적용하면 오답

# for i in board[x]:

#     q.append((i,1))

# visited[x]= 1

 

answer = []

 

while q:

    front = q.popleft()

    first = front[0]

    second=  front[1]

    visited[first]=1

    

    if second == k:

        answer.append(first)

 

    for next in board[first]:

        if visited[next]!=1:

            q.append((next,second+1))

            visited[next]=1          

 

answer.sort()

 

if len(answer)==0:

    print(-1)

else:

    for i in answer:

        print(i)

 

 

-----변경코드

 

from collections import deque

n, m, k, x = map(int, input().split())

board = [[] for _ in range(n+1)]
visited = [0] * (n+1)

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

q = deque()

#q.append((x,0))  ##
for i in board[x]:
    if visited[i]!=1:
        q.append((i,1))
        visited[i]= 1
visited[x]=1  ##정답표시

answer = []

if k==0:
    answer.append(1)
    
while q:
    front = q.popleft()
    first = front[0]
    second=  front[1]
    visited[first]=1
    
    if second == k:
        answer.append(first)

    for next in board[first]:
        if visited[next]!=1:
            q.append((next,second+1))
            visited[next]=1          

answer.sort()

if len(answer)==0:
    print(-1)
else:
    for i in answer:
        print(i)