Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- 스택
- N과M
- 가상메모리 관리
- 재귀
- 브루트포스
- python
- level0
- MYSQL
- level1
- 프로그래머스
- 파이썬
- dict
- 코딩테스트
- 가상메모리
- 힙
- dfs
- 수학
- 다이나믹 프로그래밍
- level2
- 백준
- level3
- BOJ
- DP
- BFS
- 그리디
- 운영체제
- 구현
- 다익스트라
- 딕셔너리
- programmers
Archives
- Today
- Total
동캄의 코딩도장
프로그래머스 level2 [배달] 파이썬 본문
https://programmers.co.kr/learn/courses/30/lessons/12978
코딩테스트 연습 - 배달
5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4
programmers.co.kr
실패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
'코테 > 프로그래머스' 카테고리의 다른 글
프로그래머스 level2 [수식 최대화] 파이썬 (0) | 2021.12.23 |
---|---|
프로그래머스 level2 [메뉴 리뉴얼] 파이썬 (0) | 2021.12.23 |
프로그래머스 level2 [뉴스 클러스터링] 파이썬 (0) | 2021.12.18 |
프로그래머스 level2 [괄호 변환] 파이썬 (0) | 2021.12.18 |
프로그래머스 level2 [방금그곡] 파이썬 (0) | 2021.12.18 |