GitHub ID : soohyun-dev
윤수현의 개발 공간
GitHub ID : soohyun-dev
전체 방문자
오늘
어제
  • 분류 전체보기 (918)
    • 성장기록 (49)
      • 성장기록 (3)
      • 우아한테크코스 (16)
      • 프로젝트 (15)
      • TIL (14)
      • 테오의 스프린트 (1)
    • 프로그래밍언어 (88)
      • C언어 (14)
      • HTML\CSS (12)
      • JavaScript (7)
      • React (23)
      • Python (11)
      • JAVA (14)
      • TypeScript (6)
    • 알고리즘 공부 (736)
      • 코드업 - 파이썬 (108)
      • 백준 - 파이썬 (468)
      • 백준 - 자바스크립트 (125)
      • 프로그래머스 - 파이썬 (1)
      • 프로그래머스 - 자바스크립트 (34)
    • 책 리뷰 (9)
      • 프로그래밍 (3)
      • 독서 (6)
    • 전자기기 (1)
    • 일상, 일기 (18)
    • 기술 세미나 (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 파이썬
  • 자바스크립트
  • 백준파이썬
  • 백준
  • PYTHON
  • 프론트엔드
  • 영어독해
  • 코딩테스트
  • javascript
  • 백준풀이
  • 코드업파이썬
  • 독해
  • 프로그래머스자바스크립트
  • 코딩
  • 프로그래머스풀이
  • 프로그래머스
  • 영어
  • 코테
  • 프로그래밍언어
  • 코드업

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
GitHub ID : soohyun-dev

윤수현의 개발 공간

백준/ Gold 3 문제 , 백준 파이썬 1719 , 택배 [다익스트라 알고리즘]
알고리즘 공부/백준 - 파이썬

백준/ Gold 3 문제 , 백준 파이썬 1719 , 택배 [다익스트라 알고리즘]

2022. 8. 29. 16:25

백준/ Gold 3 문제 , 백준 파이썬 1719 , 택배 [다익스트라 알고리즘]

 

 

풀이 시간

 

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

A->B 로 갈때 가장 먼저 지나는 구역이라는 것은 반대로 생각해보면 B->A 로 갈때 마지막으로 지나는 구역이라는 뜻이다. 이걸 이용해서 그래프에 이전 값을 담고 1~N+1까지 돌려서 행렬을 만들어 출력시키면된다.

 

 

문제 출처

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

 

1719번: 택배

명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하

www.acmicpc.net

 

 

 

정답

 

 

 

from cmath import inf
import heapq
import sys
input=sys.stdin.readline

N,M=map(int,input().split())
graph=[[] for _ in range(N+1)]
for i in range(M):
    a,b,c=map(int,input().split())
    graph[a].append((c,b,a))
    graph[b].append((c,a,b))

matrix=[]
for j in range(1,N+1):
    q=[(0,j)]
    dist=[inf]*(N+1)
    chart=[0]*(N+1)
    dist[j]=0
    while q:
        Z,X=heapq.heappop(q)
        if dist[X]<Z:
            continue
        for cost,next,now in graph[X]:
            cost=cost+Z
            if cost<dist[next]:
                dist[next]=cost
                chart[next]=now
                heapq.heappush(q,[cost,next])
    matrix.append(chart)
    
for i in range(1,N+1):
    for j in range(N):
        if i-1==j:
            print('-', end=' ')
        else:
            print(matrix[j][i],end=' ')
    print()

 

 

 

반응형

'알고리즘 공부 > 백준 - 파이썬' 카테고리의 다른 글

백준/ Gold 5 문제 , 백준 파이썬 1916 , 최소비용 구하기 [다익스트라 알고리즘]  (0) 2022.08.29
백준/ Gold 4 문제 , 백준 파이썬 1753 , 최단경로 [다익스트라 알고리즘]  (0) 2022.08.29
백준/ Gold 3 문제 , 백준 파이썬 1238 , 파티 [다익스트라 알고리즘]  (0) 2022.08.29
백준/ Gold 4 문제 , 백준 파이썬 13424 , 비밀 모임 [다익스트라 알고리즘]  (0) 2022.08.29
백준/ Gold 5 문제 , 백준 파이썬 5972 , 택배 배송 [다익스트라 알고리즘]  (0) 2022.08.29
    '알고리즘 공부/백준 - 파이썬' 카테고리의 다른 글
    • 백준/ Gold 5 문제 , 백준 파이썬 1916 , 최소비용 구하기 [다익스트라 알고리즘]
    • 백준/ Gold 4 문제 , 백준 파이썬 1753 , 최단경로 [다익스트라 알고리즘]
    • 백준/ Gold 3 문제 , 백준 파이썬 1238 , 파티 [다익스트라 알고리즘]
    • 백준/ Gold 4 문제 , 백준 파이썬 13424 , 비밀 모임 [다익스트라 알고리즘]
    GitHub ID : soohyun-dev
    GitHub ID : soohyun-dev
    환영합니다!😊 이곳은 저의 개발에 관한 내용들을 정리하는 공간입니다. 알고리즘 풀이에도 관심이 많아요. 좋은 하루 되세요~! github : soohyun_dev

    티스토리툴바