다익스트라

알고리 수재님의 양질의 자료는...나만 보고 ㅎㅎㅎㅎㅎㅎ

오늘은 배운거 따로 찾아서 올려야겠습니다. 알고리 최고 !!

 

다익스트라( Dijkstra ) ?

: 첨엔…다익스트라 영문명이 뭐야저게 어케 저걸 다익스트라라고 읽음 ? 했는데

ijk라는 사실을 듣고 헉! 싶었다. 이런 소소한 재미…야무지고요.

다익스트라는 최단 경로 알고리즘이다. Single Source Shortes Path Problem이다. 이산수학시간에 배웠던 것을 기반으로 설명을 적어보자면

기준 vertex(node)은 0으로 둔 뒤, 나머지는 모든 가중치를 무한으로 둔다.

기준 vertex에서 갈 수 있는 모든 edge를 무한대값에서 바꿔준 뒤, 제일 짧은 쪽으로 감.

가다가 같은 vertex를 다시 만날 시, 왔던 값이 기존 값 보다 작으면 업데이트 시켜줌을 계속 반복하면 최단 경로가 모두 업데이트 됨!

알고리 시간에 했던 문제를 다시 풀어보기 전, 다익스트라 알고리즘부터 코드를 짜보자

전에 collections에 있는 heapq와 deque를 다시 기억해보기

https://justkode.kr/python/pygorithm-2/ 요기에서 가져왔다.

deque

: 양방향 큐. stack으로도 사용 가능

from collections import deque

d = deque([1, 2, 3])
d.append(4)					# deque의 오른쪽에 4를 더함.
d.append(0)					# deque의 왼쪽에 0을 더함.
d.pop()						# deque의 가장 오른쪽 값을 지우고 반환함.
d.popleft()					# deque의 가장 왼쪽 값을 지우고 반환함.
d.extend([4, 5, 6])			# deque의 오른쪽에 iterable 한 객체의 원소들을 더함.
d.extendleft([-2, -1, 0])	# deque의 왼쪽에 iterable 한 객체의 원소들을 더함.
d.reverse()					# deque의 원소들의 순서를 뒤집음.
d.rotate(1)					# deque의 원소들의 순서를 한 칸씩 회전 시킴.
d[3]						# deque의 3번째 원소를 반환함.
d.clear()					# deque의 값을 비움.

heapq

: 일반 list를 heap처럼 사용할 수 있게 도와줌.

import heapq

h = []
heapq.heappush(h, 3)	# 첫 번째 파라미터에는 list 객체가
heapq.heappush(h, 9)	# 두 번째 파라미터에는 삽입하려는 객체가 들어간다.
heapq.heappush(h, 7)
heapq.heappush(h, 8)
heapq.heappush(h, 5)
heapq.heappush(h, 1)

for _ in range(6):
	print(heapq.heappop(h))	# 작은 값부터 출력된다.

import heapq

h = [3, 9, 1, 4, 2]
heapq.heapify(h)	# 파라미터로 list 객체를 받는다.

for _ in range(6):
	print(-heapq.heappop(h))	# 작은 값부터 출력된다.

그럼 다시 돌아와서 Dijkstra 코드 생성시, 작은값을 저장해야하니 힙큐를 사용함

코드 알고리즘은

1. 출발노드와 목표 노드 설정
2. 알고있는 모든 weight. 거리 값 부여
3. 출발 노드부터 시작하여 방문하지 않은 인접 edge의 vertex 방문. 기본 거리값은 무한대로 설정되어있으므로 짧으면 업데이트
4. 현재 노드에 인접한 모든 미방문 노드까지의 거리를 계산했다면 현재 노드는 방문한것이므로 미방문 리스트에서 제거.
5. 도착 노드가 미방문 리스트에서 제거되면 알고리즘 종료

라고….위 블로그에서 말했다… 이거 일주일동안 고민만 해봐도 못짤 것 같으니 그냥 위 블로그 코드를 공부하는 식으로 하자…

#입력
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 3
4 3 3
4 5 1
5 3 1
5 6 2

import heapq
import sys

vertex_num , edge_num  = map(int, input().split())
#노드 개수와 선 개수 입력받기
INF = 1e9
#무한대 설정
start = int(input())
#시작 노드 입력

graph = [ [] for i in range(vertex_num+1)]
#그래프 생성. 만약 vertex_num이 6이라면 0부터 6까지의 빈 리스트들이 리스트로 묶여있음
#노드는 1부터 시작하므로 0번째 부터 시작하는 리스트에서 한 칸 추가
result_distance = [INF]*(vertex_num+1)
#노드 개수만큼 최단거리 결과 리스트 만들어 준 후 모두 무한대로 초기화

for _ in range(edge_num):
  start_vertex, end_vertex , weight = map(int, input().split())
  graph[start_vertex].append((end_vertex,weight))
# 그래프의 가중치 추가. 시작 노드, 도착노드, 가중치를 입력받은 후 
# 그래프 리스트의 시작노드 숫자번째의 값에 도착노드와 가중치 입력.
# 입력받은 모습은 [ [], [(2,2),(3,5),(4,1)],[(3,3),(4,2)],...,[(3,1),(6,2)] ]
  
def dijkstra(start):
  q = []
	# 검사할 큐 생성
  heapq.heappush(q,(0,start))
	# 시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
  result_distance[start]=0
	#시작 경로1의 최단 거리는 0이므로 0으로 지정.
  while q:
	# 검사 할 큐가 비어있지 않다면 while문 실행
    current_dist, current_vertex = heapq.heappop(q)
		#비교할 노드의 번호와 현재 거리를 q에서 뽑아오기. 
		#비교할 현재 노드는 1로써 거리는 0이다
    if result_distance[current_vertex] < current_dist:
      continue
			#만약 비교할 노드와의 거리가 이미처리된 거리로써, 작다면 처리된것이므로 skip
    for i in graph[current_vertex]:
      sum_distance = current_dist + i[1]
			# current_vertex(1)의 그래프의 도착노드의 가중치값과 현재 노드 합
      if sum_distance < result_distance[i[0]]:
			#그 합이 결과테이블(처음에 무한대해줬던 값)보다 작다면
        result_distance[i[0]] = sum_distance
        heapq.heappush(q,(sum_distance,i[0]))
				#heapq로써 q의 검사할 큐에 (총거리,노드번호)의 형태로 넣어준 뒤 다시
				#이 ()세트들을 검사
        
dijkstra(start)
#1번 노드를 기준으로 다익스트라 알고리즘 실행
print(*result_distance)

아…다른사람꺼 보고 해도 존 어려운것이다…..

그럼 문제를 풀어보자 !

 

 

 

백준 10282 해킹

최흉최악의 해커 욤3씨….

import heapq
INF = 1e9

try_num = int(input())

def dijkstra(relation_table, hacking_computer_num, computer_num,relation_num):
    result = [0,0]
    #총 감염 컴터수, 마지막 컴터 감염 시간정보
    hacking_time = [None] +[INF] * computer_num
    #모든 컴퓨터에 무한대의 시간을 부여한다. None을써줌으로써 0번째는 없다는걸 의미
    hacking_time[hacking_computer_num]=0
    #무한대의 시간이 부여된 모든 테이블 중, 해킹당한 첫번째 컴퓨터에 시간0을 부여.
    
    q = [(0,hacking_computer_num)]
    #먼저 검사할 첫번째 해킹 컴퓨터와 그 해킹 시간을 입력.
    while q:
        hack_time,now_com = heapq.heappop(q)
        #주변 해킹관계를 검사할 현재 기준 컴퓨터. 첫 시도에선 첫번째 해킹 컴퓨터와 그 시간 꺼내기
        for i in range(relation_num):
            if relation_table[i][1] in q[1]:
                result[0] += 1
                result[1] += i[2]
                heapq.heappush(q, (i[2],i[0]))
    return result

while(try_num != 0):
    
    computer_num, relation_num, hacking_computer_num = map(int,input().split())
    relation_table = []
    for i in range(relation_num):
        a,b,s = map(int,input().split())
        relation_table.append((a,b,s))
        #relation_table = [ (2,1,5), (3,2,5) ]
    print(*dijkstra(relation_table,hacking_computer_num,computer_num ,relation_num))
    try_num -= 1

이론상 돌아감….그치만? 컴파일 오류난다 ~

….