전보

2023. 1. 20. 03:52· Problem Solving/최단 경로

이 문제는 이것이 코딩테스트다 262페이지 문제이다. 

최단 거리문제는 전부 똑같은 유형이다. 정답이 거의 동일하고 출력부분만 다른 경우가 많다.

이 문제는 입력의 값이 크기에 우선순위큐다익스트라 알고리즘을 이용하여야 한다.

다익스트라 구현 방식을 이해를 하여야 한다. 그리고 거리비용이 현재보다 커질 때는 가지치기(branch and bound)를 미리 해주어야 한다.는 것을 알아야 한다. 

https://yunzae.tistory.com/94

 

최단경로(다익스트라,플로이드워셜)

최단경로는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기'문제라고도 불린다. 최단 경로 알고리즘 유형에서는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 정립

yunzae.tistory.com

아래는 나의 코드이다.

 

import sys
import heapq
N,M,C=map(int,sys.stdin.readline().split())
INF=int(1e9)
distance=[INF]*(N+1)

graph=[]
for _ in range(N+1):
    graph.append([])

for i in range(1,M+1):
    temp=list(map(int,sys.stdin.readline().split()))
    graph[temp[0]].append((temp[1],temp[2]))



def dijkstra(start):
    q=[]
    heapq.heappush(q,(0,start))
    distance[start]=0
    while q:
        dist,now = heapq.heappop(q)
        if distance[now] <dist:
            continue
        for next in graph[now]:
            next_node=next[0]
            next_dist=next[1]+dist
            if distance[next_node]>next_dist:
                distance[next_node]=next_dist
                heapq.heappush(q, (next_dist, next_node))

dijkstra(C)

city_count=0
max_distance=0
for result in distance:
    if result!= INF:
        city_count+=1
        if result>max_distance:
            max_distance=result

print(city_count-1,max_distance)

 

아래는 예시코드이다.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수, 시작 노드를 입력받기
n, m, start = map(int, input().split())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    x, y, z = map(int, input().split())
    # X번 노드에서 Y번 노드로 가는 비용이 Z라는 의미
    graph[x].append((y, z))

def dijkstra(start):
   q = []
   # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
   heapq.heappush(q, (0, start))
   distance[start] = 0
   while q: # 큐가 비어있지 않다면
        # 가장 최단 거리가 짧은 노드에 대한 정보를 꺼내기
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

# 다익스트라 알고리즘을 수행
dijkstra(start)

# 도달할 수 있는 노드의 개수
count = 0
# 도달할 수 있는 노드 중에서, 가장 멀리 있는 노드와의 최단 거리
max_distance = 0
for d in distance:
    # 도달할 수 있는 노드인 경우
    if d != 1e9:
        count += 1
        max_distance = max(max_distance, d)

# 시작 노드는 제외해야 하므로 count - 1을 출력
print(count - 1, max_distance)

'Problem Solving > 최단 경로' 카테고리의 다른 글

BOJ1916 최소비용 구하기  (0) 2023.03.30
BOJ1446 지름길  (0) 2023.03.21
BOJ18352 특정 거리의 도시 찾기  (0) 2023.03.20
미래도시  (0) 2023.01.19
'Problem Solving/최단 경로' 카테고리의 다른 글
  • BOJ1916 최소비용 구하기
  • BOJ1446 지름길
  • BOJ18352 특정 거리의 도시 찾기
  • 미래도시
윤재에요
윤재에요
윤재에요
yunzae.log
윤재에요
전체
오늘
어제
  • 분류 전체보기 (435)
    • Computer Science (115)
      • 데이터베이스 (50)
      • 네트워크 (18)
      • 소프트웨어 공학 (1)
      • 알고리즘 (10)
      • 자료구조 (9)
      • 컴퓨터구조 (0)
      • 운영체제 (0)
      • 데이터 통신 (16)
      • 프로그래밍언어론 (11)
    • Project (20)
      • 후크(Flutter) (1)
      • BDSR로그북(App,BackEnd) (2)
      • 나만의 주점(STM32,Arduino,androi.. (9)
      • 공다(App,BackEnd) (2)
      • 카카오쇼핑 클론코딩 (4)
      • 암호화폐자동매매 (2)
    • Problem Solving (205)
      • 자바 문법 (20)
      • 파이썬 문법,함수 (6)
      • 그리디 (5)
      • 구현 (43)
      • DFS (3)
      • BFS (17)
      • 정렬 (15)
      • 이진 탐색 (16)
      • 다이나믹 프로그래밍 (6)
      • 최단 경로 (5)
      • 그래프 (1)
      • 자료구조 (5)
      • 투포인터 (15)
      • SQL (41)
      • 구간합 (7)
    • I leaned (78)
      • 스프링,스프링부트 (31)
      • Git (6)
      • JAVA (5)
      • Etc (30)
    • 취업 (15)
      • PT면접 (6)
      • 기술면접 (9)
      • 인성면접 (0)
    • log (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 글쓰기

공지사항

인기 글

태그

  • 참조 무결성
  • 재시도
  • 이것이 코딩테스트다.
  • 이것이코딩테스트다
  • 최단 거리
  • 다익스트라
  • 제약 사항
  • weak entity
  • 먀
  • 데이터베이스
  • Relationship model
  • 힙큐
  • 카카오테크캠퍼스
  • 효율적인화폐구성
  • 다이나믹
  • 최단거리
  • 부품찾기
  • 이것이 코딩테스트다
  • 교환정렬
  • 다이어그램
  • DP
  • 파이썬
  • 개미전사
  • 그리디
  • 플로이드 워셜
  • 기수정렬
  • E-R Model
  • 계수정렬
  • UML
  • 다이나믹프로그래밍

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
윤재에요
전보
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.