백준 18352_특정거리도시찾기

특정 거리의 도시 찾기(백준 18352)

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

BFS를 적용하는 문제인 것은 파악할 수 있었다.
처음에는 ‘간선’에 임의로 ‘가중치’를 부여하는 방식을
사용해봤으나
코드의 가독성이 떨어졌고,
추가적으로 ‘오답’으로 판정되었다

그래서 ‘노드’에 ‘거리’를 저장하는
방식을 취하였고,
‘일정 거리’ 이하라면 BFS를 통해 가리키는 노드를 탐색,
해당 노드의 거리가 ‘일정 거리’라면, 정답 배열에 넣어주는
방식이다

Code

import sys
import queue
import math

# 단방향 간선으로 주어진다고 명시함

nNum,eNum,distanceK,start = map(int,sys.stdin.readline().split())
#인접 리스트
edge = [[] for _ in range(nNum)]

for i in range(eNum):
    st,to = (map(int,sys.stdin.readline().split()))
    edge[st-1].append(to-1)

def Bfs(start,edge,distance):
    que = queue.Queue()
    que.put(start)              # 시작지점 넣어준다
    result = []
    visit = [False] * len(edge) # 
    distance[start] = 0
    
    while not que.empty():
        node = que.get()

        if distance[node] == distanceK: # 현재 노드의 거리가 목표거리와 같다면
            result.append(node)
        elif distance[node] < distanceK: # 현재 노드의 거리가 목표거리보다 작다면
            for neigbor in edge[node]:
                if not visit[neigbor] and distance[neigbor] > distance[node]:
                    distance[neigbor] = distance[node] + 1 # 이전 노드보다 + 1
                    que.put(neigbor)
                    visit[neigbor] = True
        # 현재 노드의 거리가 목표 거리를 넘어서는 경우는 계산 필요 없음

    return result

# 가중치 초기화
init_dis = [math.inf] * nNum
resultAr = Bfs(start - 1, edge,init_dis)

if resultAr:
    resultAr.sort()
    for i in resultAr:
        print(i + 1)
else:
    print(-1)

해결 아이디어

1. 시작 시, 모든 노드의 거리를 ‘inf’로 초기화하며,
   시작하는 노드의 거리는 0으로 한다
2. 방문한 노드의 거리가 ‘일정 거리’라면 정답 배열에,
   ‘일정거리’ 미만이라면 해당 노드가 가리키는 노드들의
   거리를 ‘해당 노드 거리 + 1’로 만들고, 큐에 넣어준다
   
3. 정답 배열을 반환하며, 배열을 오름차순으로 출력
   이 때, 배열이 비어있다면 -1 을 반환한다