<PART 3> Q15.백준 18352번: 특정 거리의 도시 찾기

https://www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

- input.txt파일 만들었을 때 코드

from collections import deque
import sys
 
sys.stdin = open('input.txt')
 
def bfs(start):
    global answer
    # 시작하는 노드를 먼저 queue에 넣기
    queue = deque([start])
    queue.append(start)
    #큐가 빌때까지 실햄
    while queue:
        x = queue.popleft()
        for i in graph:
            # 해당 노드가 graph에 있다면 연결된 노드를 추가
            if i[0] == x:
                # 처음 노드라면 추가시키기
                if result[i[1]] == 0:
                    queue.append(i[1])
                    #추가시킬 때 이전 노드의 결과값에 +1시키기
                    result[i[1]] += result[i[0]] + 1
                # # 처음이 아니면 최단거리가 아니므로 추가 x
                else:
                    continue
            # 해당 노드가 graph에 없다면 탈출
            else:
                continue
    #맨 처음 노드는 계산편하게 하기 위해 넣었으므로 빼기
    result.pop(0)
    # 최단 거리가 k인 도시를 오름차순으로 출력
    for i in range(len(result)):
        if result[i] == k:
            answer.append(i+1)
    answer
    #아무것도 없어서 answer가 빈리스트라면
    if not answer:
        answer = [-1]
    # 끝나면 결과값 출력
    return answer
 
for test in range(3):
    #도시개수 n, 도로개수 m, 거리정보 k, 출발 도시 번호 start 받기
    n,m,k,start = map(int,input().split())
 
    #단방향 도로 입력받기
    graph = []
    for i in range(m):
        graph.append(list(map(int,input().split())))
    #최단거리 저장해놓을 1차원 리스트, 노드 1부터 시작하므로 n+1개 생성 0으로 초기화
    result = [0 for i in range(n+1)]
    answer = []
    bfs(start)
    for i in answer:
        print(i)

맨 처음 이렇게 작성했는데 제출할 떄 시간초과로 오류가 났다.
그래서 왜인지 이유를 보았다. graph에다가 값을 바로 넣어주면 queue에서 나온 원소가 graph를 전부 n번 돌아야 한다. 그래서 이러한 이유때문에 시간 초과가 떴다.
해결 방법은 graph를 만들 때 노드와 노드를 넣지말고 인덱스번호자체가 노드번호가 되게 하고 그 안에 연결된 노드의 값들을 append해야한다. 이렇게 하면 나중에 while문을 돌릴 때 인덱스로 접근만하면 그값에 연결된 노드만 꺼낼 수 있다.

- 제출용

from collections import deque
import sys
 
input = sys.stdin.readline
n,m,k,x = map(int,input().split())
 
graph = [[] for _ in range(n+1)]
for i in range(m):
   a,b = map(int,input().split())
   graph[a].append(b)
 
distance = [-1] * (n+1)
distance[x] = 0
 
def bfs(start):
    queue = deque([start])
    while queue:
        now = queue.popleft()
        for next_node in graph[now]:
            if distance[next_node] == -1:
                distance[next_node] = distance[now] + 1
                queue.append(next_node)
    answer = [i for i in range(len(distance)) if distance[i] == k]
    if not answer:
        answer = [-1]
    print(*answer, sep="\n")
 
bfs(x)
 

import sys
 
input = sys.stdin.readline
n,m,k,x = map(int,input().split())
 
graph = [[] for _ in range(n+1)]
for i in range(m):
   a,b = map(int,input().split())
   graph[a].append(b)
 
distance = [-1] * (n+1)
distance[x] = 0
 
def bfs(start):
    queue = []
    queue.append(start)
    while queue:
        now = queue.pop(0)
        for next_node in graph[now]:
            if distance[next_node] == -1:
                distance[next_node] = distance[now] + 1
                queue.append(next_node)
    answer = [i for i in range(len(distance)) if distance[i] == k]
    if not answer:
        answer = [-1]
    print(*answer, sep="\n")
 
bfs(x)
 

실행은 되나, 백준에서 제출 시 시간 초과가 뜹니다.