특정거리의 도시 찾기 Python 정리 및 구현 (백준 18352, 삼성 SW 역량테스트 기출)

특정거리의 도시 찾기

백준 18352:

Edge case

1. 문제조건

• 오름차순 확인
• 인덱스가 1부터 시작하는 것 확인
• 값의 범위가 크므로, $O(NlogN)$으로 문제 풀 생각
• 시작지점에서 이미 거리가 k이상이면 더 알아볼 필요도 없음 (3번 풀이 참고)

---

Code

1. Dijkstra

• list 사용
• 시간초과

# 백준
# 특정거리의 도시 찾기
# dfs
# 1트 Dijkstra로 풀었으나 시간초과

#@@ index가 1번부터 주어짐
import sys
input = sys.stdin.readline
INF = int(1e9)


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

graph = [[] for _ in range(n+1)]    # n+1개 생산해서 1부터 시작하는 노드번호에 맞추기
v = [False] * (n+1)
d = [INF] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)  # 어디서부터 어디로 가는지
#-----------------#

# 방문하지 않은 노드 중에 최단거리가 가장 짧은 노드의 번호를 반환
def get_smallest_node():
    min_value = INF
    index = 0   # 가장 최단거리가 짧은 인덱스
    for i in range(1, n+1):
        if d[i] < min_value and not v[i]:
            min_value = d[i]
            index = i
    return index

def dijkstra(s):
    d[s] = 0    # 시작지점의 거리는 0
    v[s] = True # 방문 표시
    for i in graph[s]:  # 목적지 다 빼줘
        d[i] = 1    # 가중치 저장
    
    for i in range(n-1):
        now = get_smallest_node()   # 최단거리가 가장 짧은 노드를 꺼내서 
        v[now] = True               # 방문처리하기
        for j in graph[now]:        # 현재 방문한 노드에서 다른곳으로 가는길 탐색
            cost = d[now] + 1       # 현재위치 찍고 가는 경우의 수
            if cost < d[j]:         # 위치까지 가는 다른 길이 더 길면
                d[j] = cost         # cost로 업데이트

def check():
    flag = False
    for i in range(1, n+1):
        if d[i]==k:
            print(i)
            flag = True
    if flag == False:
        print(-1)

if __name__ == "__main__":
    dijkstra(x)
    check()

# 각 노드로 향하는 최단거리가 저장돼있는 배열 d에서 원소가 k인 애들의 index만 빼와

---

2. Dijkstra

• 우선순위 큐 사용

# 백준 18352
# 특정거리의 도시 찾기
# 우선순위큐 Dijkstra로 풀기

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)


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

graph = [[] for _ in range(n+1)]    # n+1개 생산해서 1부터 시작하는 노드번호에 맞추기
v = [False] * (n+1)
d = [INF] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)  # 어디서부터 어디로 가는지

def dijkstra(s):
    q = []
    heapq.heappush(q, (0, s))   # 튜플의 앞부터 정렬됨
    d[s] = 0
    while q:
        dist, now = heapq.heappop(q)
        if d[now] < dist:    # 갓 뽑은 애보다 지금 배열에 있는게 더 작다? >> 이미 업뎃된(방문된) 노드임
            continue

        for i in graph[now]:
            cost = dist + 1
            if cost < d[i]:
                d[i] = cost
                heapq.heappush(q, (cost, i))
def check():
    flag = False
    for i in range(1, n+1):
        if d[i]==k:
            print(i)
            flag = True
    if flag == False:
        print(-1)
     
dijkstra(x)
check()

---

3. BFS

# 백준 18352
# bfs로 풀기

import sys
from collections import deque
input = sys.stdin.readline
INF = int(1e9)

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

graph = [[] for _ in range(n+1)]    # n+1개 생산해서 1부터 시작하는 노드번호에 맞추기
v = [False] * (n+1)
d = [INF] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)  # 어디서부터 어디로 가는지
#-----------------#


def bfs(s):
    q = deque()
    q.append([0, s])
    
    while q:
        w, now = q.popleft()
        v[now] = True   # 방문 표시
        if w > k:   # 시작지점이 이미 k보다 높다면 패쓰
            continue
        for i in graph[now]:
            if v[i]: continue
            d[i] = min(d[i], w + 1)
            q.append([d[i], i])


def check():
    flag = False
    for i in range(1, n+1):
        if d[i]==k:
            print(i)
            flag = True
    if flag == False:
        print(-1)

bfs(x)
check()