[Python] 이코테 특정 거리의 도시 찾기 (백준 18352)

문제

💡아이디어

1. 거리 문제이므로 BFS를 떠올렸다.

 

2. 도시/간선 배열 graph와 거리 배열 distance를 선언했다.

graph는 이중 배열로 미리 초기화해두어 for문으로 입력받을 수 있도록 했다.

distance는 -1로 초기화하고 출발 노드는 0으로 지정했다.

 

3. 이동 가능한 모든 노드를 BFS로 확인하며 방문 여부를 체크한다.

while queue로 큐가 빌 때까지 반복문을 돌며, 현재 노드를 큐에서 pop하고 인접 노드를 큐에 담아서 거리 정보를 더했다.

 

4. 거리 정보 체크

처음엔 리스트 타입의 check를 떠올렸으나, 메모리의 문제로 불리언 타입의 check 변수로 변경했다.

 

정답

# 백준 18352

import sys
from collections import deque
# 도시 개수, 도로 개수, 거리 정보, 출발 도시 번호
N, M, K, X = map(int, sys.stdin.readline().split())

# 1번 도시부터 N번 도시 배열 초기화
graph = [[] for _ in range(N+1)]
#간선정보 입력
for _ in range(M):
  A, B = map(int, sys.stdin.readline().split())
  graph[A].append(B)

# 출발 도시로부터 거리를 저장
distance = [-1 for _ in range(N+1)]
distance[X] = 0

# BFS 시작
queue = deque()
queue.append(X)
  
while queue:
  v = queue.popleft()
  # 현재 도시에서 갈 수 있는 모든 도시
  for i in graph[v]:
    if distance[i] != -1:
      continue
    else:
      distance[i] = distance[v] + 1
      queue.append(i)

# 거리 정보 체크
check = False
for i in range(N+1):
  if distance[i] == K:
    check = True
    print(i)

if check == False:
  print(-1)

 

시간복잡도 : O(N+M)

 

 

삽질 내용

처음엔 아래 코드로 풀었는데, 백준에서 시간복잡도에 걸렸다.

from collections import deque
# 도시 개수, 도로 개수, 거리 정보, 출발 도시 번호
N, M, K, X = map(int, input().split())

# 1번 도시부터 N번 도시 배열 초기화
graph = [[] for _ in range(N+1)]
#간선정보 입력
for _ in range(M):
  A, B = map(int, input().split())
  graph[A].append(B)

# 출발 도시로부터 거리를 저장
distance = [-1 for _ in range(N+1)]
distance[X] = 0

# BFS 시작
queue = deque()
queue.append(X)
  
while queue:
  v = queue.popleft()
  # 현재 도시에서 갈 수 있는 모든 도시
  for i in graph[v]:
    if distance[i] != -1:
      continue
    else:
      distance[i] = distance[v] + 1
      queue.append(i)

# 거리 정보 체크
check = False
for i in range(N+1):
  if distance[i] == K:
    check = True
    print(i)

if check == False:
  print(-1)

 

해결 삽질

input 대신 sys.stdin.readline 사용하는 것을 생활화하자!

대량의 데이터를 처리할 때 유용하기 때문!

이번 문제의 경우 각 변수의 조건이 아래와 같았다 ..

 (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N)