https://programmers.co.kr/learn/courses/30/lessons/12978#
알고리즘 분류
- BFS
문제풀이
처음엔 방문한 노드를 저장하는 visited리스트를 사용해 방문했냐 안했냐를 확인해서 탐색했다. 그러나 이럴 경우 나중에 돌아서 방문하는 경우가 더 빠를수도 있다는 것이다.
방문한 노드를 저장하는 변수(visit)을 사용하셨을 겁니다.
이미 방문한 노드를 다시 방문하지 않기 위해 사용하는 것인데,
중요한 것은 특정 노드를 방문했느냐 안했느냐(0 or 1)가 아닙니다.
특정 노드를 방문하는데 걸린 시간 중 최소의 값을 visit에 저장하고
특정 노드를 방문하는데 그 값보다 큰 시간이 걸리는 경우에는 탐색하지 않는 식으로 구현해보세요.기본 틀은 다음과 같다.
딕셔너리로 음식점과 마을을 연결해 시간을 저장한다.
각 노드마다 최소의 시간을 저장하기 위한 visited딕셔너리를 K의 최대값인 500001로 초기화해준다.
예시)
{1: 500001, 2: 8, 3: 500001, 4: 500001, 5: 500001}
{1: 500001, 2: 8, 3: 500001, 4: 2, 5: 500001}
{1: 16, 2: 8, 3: 500001, 4: 2, 5: 500001}
{1: 16, 2: 8, 3: 11, 4: 2, 5: 500001}
{1: 16, 2: 8, 3: 11, 4: 2, 5: 10}
{1: 4, 2: 8, 3: 11, 4: 2, 5: 10}
{1: 4, 2: 8, 3: 11, 4: 2, 5: 4}
{1: 4, 2: 8, 3: 11, 4: 2, 5: 4}
{1: 4, 2: 6, 3: 11, 4: 2, 5: 4}
{1: 4, 2: 6, 3: 5, 4: 2, 5: 4}
이후 1을 제외한 2번노드부터 K 이하의 시간인지 확인하고 결과를 더해주면 정답이다.
소스코드
from collections import deque
def solution(N, road, K):
dic={i:[] for i in range(1,N+1)}
for r in road:
a,b,w=r
dic[a].append((b,w))
dic[b].append((a,w))
queue=deque()
queue.append((1,0))
visited={i:500001 for i in range(1,N+1)}
while queue:
t,w=queue.popleft()
for i in dic[t]:
target,weight=i
tmp=w+weight
if visited[target]>=tmp:
visited[target]=tmp
queue.append((target,visited[target]))
result=1
for i in range(2,N+1):
if visited[i]<=K:
result+=1
return result