프로그래머스 level2 [배달] 파이썬

https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

실패1

맨처음에 dfs로 구현하여 풀려고 하였다. for문을 이용해 방문하지 않은 모든 노드가 있으면, 재귀적으로 dfs문을 실행하도록 설계하였다.

#프로그래머스 배달 dfs
def solution(N, road, K):
    answer = 0
    visited=[0]*(N+1)
    link=[[10001]*(N+1) for _ in range(N+1)]
    for r in road:
        a,b,cost=map(int,r)
        link[a][b]=min(link[a][b],cost)
        link[b][a]=min(link[b][a],cost)
    lst={}
    def dfs(node,cost):
        visited[node]=1
        if cost<=K:
            lst[node]=1
            for i in range(1,N+1):
                if visited[i]==0 and link[node][i]!=10001:
                    dfs(i,cost+link[node][i])
        visited[node]=0
    dfs(1,0)
    answer=len(lst)
    return answer

마지막 테스트케이스에서 시간초과가 발생하였다.

 

실패2

방법을 바꿔, 모든 노드의 방문 여부를 따지는 것이 아닌, 입력받은 링크만 반복하도록 for문을 바꾸었다.

#프로그래머스 배달 dfs
def solution(N, road, K):
    answer = 0
    visited=[0]*(N+1)
    link=[[] for _ in range(N+1)]
    for r in road:
        a,b,cost=map(int,r)
        link[a].append([b,cost])
        link[b].append([a,cost])
    lst={}
    def dfs(node,cost):
        visited[node]=1
        if cost<=K:
            lst[node]=1
            for i in range(len(link[node])):
                if visited[link[node][i][0]]==0:
                    dfs(link[node][i][0],cost+link[node][i][1])
        visited[node]=0
    dfs(1,0)
    answer=len(lst)
    return answer

그럼에도 불구하고 역시 시간초과가 발생하였다.

 

성공

결국에 bfs로 변경하여 풀었다.

#프로그래머스 배달 bfs
def solution(N, road, K):
    answer = 0
    from collections import deque
    link=[[] for _ in range(N+1)]
    visit=[500001]*(N+1)
    for r in road:
            a,b,cost=map(int,r)
            link[a].append([b,cost])
            link[b].append([a,cost])
    lst={}
    def bfs(node,cost):
        q=deque([])
        q.append((node,cost))
        while q:
            n,c=q.popleft()
            visit[n]=c
            if c<=K:
                lst[n]=1
                for i in range(len(link[n])):
                    if visit[link[n][i][0]]>(c+link[n][i][1]):
                        visit[link[n][i][0]]=(c+link[n][i][1])
                        q.append((link[n][i][0],(c+link[n][i][1])))
    bfs(1,0)
    answer=len(lst)
    return answer