[이코테] DFS/BFS_특정 거리의 도시 찾기 (python)

juyeon·2022년 7월 27일

python 알고리즘

이것이 취업을 위한 코딩 테스트다

목록 보기

41/58

문제

나의 풀이

1. colab에선 맞았지만, 백준에서는 시간초과! -> 실패

아이디어
: 출발 노드에서 일정한 거리(최소값일때)의 노드를 찾는 것. 그렇다면, 거리를 1씩 증가시키면서 찾는건 어떨까? 즉 원하는 거리(층)이 나올때까지 한층씩 제거하기.
-> BFS

from collections import deque
import sys
input = sys.stdin.readline

n, m, k, x = map(int, input().split()) #도시 개수 n, 도로 개수 m, 거리 정보 k, 출발 도시 x
city = [[] for _ in range(n + 1)] # 빈 도시 정보 list
for i in range(m): # 각 도시별 연결된 도로 정보 list에 담기
    c, road = map(int, input().split())
    city[c].append(road)
distance = [-1] * (n + 1) # 출발 도시로부터의 거리 list
distance[x] = 0 # 출발 도시의 거리 = 0

q = deque([x]) # 출발 도시부터 처리
    
while q: # q가 빌때까지
    c = q.popleft() # 큐에서 원소를 하나 뽑아 출력
    for i in city[c]: # 인접 도시 탐색
        if distance[i] > k:
            break
        if distance[i] == -1: # 아직 방문하지 않았다면
            q.append(i) # 큐에 추가
            distance[i] = distance[c] + 1 # 출발 도시로부터의 거리 입력
            
answer = False                
for i in range(1, n + 1):
    if distance[i] == k:
        answer = True
        print(i)
        
if answer == False: # 만약 k거리의 도시가 존재하지 않는다면
    print(-1)

: 아니 왜 시간초과지?!

이걸로 시간초과는 해결.

import sys
input = sys.stdin.readline

근데..이번엔 오답이 뜸. why?

if distance[i] == k: # 만약 출발 도시로부터의 거리가 k라면
	answer = True
	print(i) # 도시 출력

: 이렇게 하면, 도시 번호를 오름차순으로 출력할 수 없다! 결국 for문 따로 돌려야함.

while문에 answer = True를 안 넣은 이유
: 넣게되면, 만약 distance[i] > k 인 경우가 없을 경우, answer = True를 할 수 없게 되니까.

2. 성공

from collections import deque

# 도시 개수 n, 도로 개수 m, 최단 거리 k, 출발 도시 x
n, m, k, x = map(int, input().split())

# 도시 간 연결 정보 초기화
city = [[] for _ in range(n+1)]
# 연결된 도시 정보 저장
for _ in range(m):
    a, b = map(int, input().split())
    city[a].append(b)

# 거리 정보 초기화
distance = [-1] * (n+1)
distance[x] = 0 # 출발 도시의 거리 = 0

# x 도시에서 출발
q = deque([x])
# 계속 도시가 연결되어 있는 한
while q:
    name = q.popleft() # 현재 출발 도시
    for c in city[name]: # 연결된 도시 탐색
        if distance[c] == -1: # 아직 탐색 전이면
            distance[c] = distance[name] + 1 # 거리 +1
            q.append(c) # 다녀갈 도시에 추가
            
if k in distance: # k 거리의 도시가 있다면
    for city_name, dist in enumerate(distance):
        if dist == k:
            print(city_name)
else: # k 거리의 도시가 없다면
    print(-1)

메모리: 98684kb, 시간: 2004ms

다른 사람 풀이

책의 풀이: 엥 시간초과네? -> sys..로 해결

from collections import deque
import sys
input = sys.stdin.readline

n, m, k, x = map(int, input().split()) #도시 개수 n, 도로 개수 m, 거리 정보 k, 출발 도시 x
city = [[] for _ in range(n + 1)] # 빈 도시 정보 list
for i in range(m): # 각 도시별 연결된 도로 정보 list에 담기
    c, road = map(int, input().split())
    city[c].append(road)
distance = [-1] * (n + 1) # 출발 도시로부터의 거리 list
distance[x] = 0 # 출발 도시의 거리 = 0

q = deque([x]) # 출발 도시부터 처리
while q: # q가 빌때까지
    c = q.popleft() # 큐에서 원소를 하나 뽑아 출력
    for i in city[c]: # 인접 도시 탐색
        if distance[i] == -1: # 아직 방문하지 않았다면
            q.append(i) # 큐에 추가
            distance[i] = distance[c] + 1 # 출발 도시로부터의 거리 입력

answer = False
for i in range(1, n + 1):
    if distance[i] == k: # 만약 출발 도시로부터의 거리가 k라면
        print(i) # 도시 출력
        answer = True                
if answer == False: # 만약 k거리의 도시가 존재하지 않는다면
    print(-1)