고도고도
🍎🍏
고도고도
전체 방문자
7,920
오늘
0
어제
26
  • 분류 전체보기 (149) N
    • 🔨 프로젝트 (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • 💻 개발 (43) N
      • TIL (16)
      • Android (6)
      • Kotlin (4)
      • Flutter (9) N
      • Node.js (5)
      • Error (3) N
    • ✏️ 알고리즘 (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • ✍️ 코테 준비 (44)
      • Math (1)
      • Implementation (3)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (1)
      • DFS, BFS (5)
      • Shortest Path (2)
      • Two Pointer (4)
      • MST (0)
    • 📚 CS (6)
      • Operating System (6)
    • ⛹️ 라이프 (50)
      • 2020 겨울방학 모칵코(팀) (13)
      • 2020 겨울방학 모각코(개인) (13)
      • 2021 여름방학 모칵코(팀) (8)
      • 2021 여름방학 모각코(개인) (7)
      • 코딩 테스트 (1)
      • 회고 (7)

블로그 메뉴

  • 홈
  • 깃허브
  • 링크드인

인기 글

  • [TIL] 22.03.13
    2022.03.13
    [TIL] 22.03.13
  • [문자열 / Kotlin] 2020 KAKAO⋯
    2022.03.11
    [문자열 / Kotlin] 2020 KAKAO⋯
  • [TIL] 22.03.20
    2022.03.20
    [TIL] 22.03.20
  • [퍼듀 일기] 어느덧 한 달째
    2022.03.01
    [퍼듀 일기] 어느덧 한 달째
  • [퍼듀 일기] 적응 완료
    2022.03.05
    [퍼듀 일기] 적응 완료

최근 글

  • [Flutter] ModalBottomSheet가⋯
    2022.08.09
    [Flutter] ModalBottomSheet가⋯
  • [Error / Gradle] The current⋯
    2022.08.09
    [Error / Gradle] The current⋯
  • [Flutter / Dart] What is Equa⋯
    2022.08.06
    [Flutter / Dart] What is Equa⋯
  • [Flutter] BLoC 패턴으로 자동⋯
    2022.07.26
    [Flutter] BLoC 패턴으로 자동⋯
  • [Flutter / Dart] What is Sing⋯
    2022.07.21
    [Flutter / Dart] What is Sing⋯

최근 댓글

  • 잘보고 갑니다~
    개갓세
  • 좋은 글이네요
    날인로세
  • 잘 보고 갑니다^^
    프로퍼티
hELLO · Designed By 정상우.
고도고도

🍎🍏

⛹️ 라이프/2020 겨울방학 모각코(개인)

[코독하구만 팀] 2021.01.13(수) - 4주차 개인 결과

2021. 1. 13. 21:25

- 목표 -

codekodo.tistory.com/26

 

[코독하구만 팀] 2021.01.13(수) - 4주차 개인 목표

목표 : 최단 경로를 탐색하는 알고리즘인 다익스트라 알고리즘의 개념을 정리하고 관련된 실습 문제 3문제를 풀어본다. 이후 백준에서 관련된 문제를 풀어봄으로써 이를 응용하는 법까지 학습

codekodo.tistory.com

 

다익스트라란?

최단 경로를 탐색하는 알고리즘의 한 종류로 정점들 사이의 가중치를 비교하는 과정을 통해 최단 경로를 탐색한다.

 

해당 그림에서 정점과 간선의 가중치를 표로 나타내면 다음과 같다.

특정 행에서 특정 열로 이동할 때 발생하는 가중치를 나타낸 표이다.

인접하지 않은 경우 INF, 방향성에 의해 도달할 수 없을 때는 X로 나타내었다.

  A(여기로) B C D E F
A(여기에서) 0 10 15 INF INF INF
B X 0 INF 12 INF 15
C X INF 0 INF 10 INF
D INF X INF 0 INF 1
E INF INF X INF 0 X
F INF X INF X 5 0

 

(방문한 노드는 노란색으로 표시)

1. A와 인접한 B, C와의 최단 거리를 구한다.

A B C D E F
0 10 15 INF INF INF

 

2. B와 인접한 D, F와의 최단 거리를 구한다.

A B C D E F
0 10 15 22 INF 27

 

3. C와 인접한 E와의 최단 거리를 구한다.

A B C D E F
0 10 15 22 25 27

 

4. D와 인접한 F와의 최단 거리를 구한다. (27에서 23으로 갱신)

A B C D E F
0 10 15 22 25 23

 

5. F와 인접한 E와의 최단 거리를 구한다. (모든 정점을 방문)

A B C D E F
0 10 15 22 25 23

 

1. 다익스트라

최소힙을 이용하였고 모든 정점을 방문하면 갱신 과정을 종료한다. 단순히 최단 경로의 값을 출력하는 것이 아닌 최단 경로 과정(?)을 출력해야 하므로 최단 경로로 갱신 될 때 방문하는 정점을 새로운 dict형 변수에 저장한다.

 

import heapq

def dijkstra(v_dic, v_list, V, E, src, dst):
    INF = float('inf')
    distance = {}
    for i in range(V):
        distance[v_list[i]] = INF
    distance[src] = 0
    queue = []
    prev = {}
    for i in range(V):
        prev[v_list[i]] = []
    found = {}
    for i in range(V):
        found[v_list[i]] = False
    
    heapq.heappush(queue, [0, src])
    while queue:
        v = heapq.heappop(queue)
        found[v[1]] = True
        for node_weight in v_dic[v[1]]:
            if (found[node_weight[0]]):
                continue
            if (distance[node_weight[0]] > distance[v[1]] + node_weight[1]):
                distance[node_weight[0]] = distance[v[1]] + node_weight[1]
                heapq.heappush(queue, [distance[node_weight[0]], node_weight[0]])
                prev[node_weight[0]] = [v[1], node_weight[0], node_weight[1]]
    return prev

def main():
    V, E = map(int, input().split())
    v_list = input().split()
    v_dic = {}
    for i in v_list:
        v_dic[i] = []

    for _ in range(E):
        i, j, c = input().split()
        c = int(c)
        v_dic[i].append([j,c])
    
    src, dst = input().split()
    prev = dijkstra(v_dic, v_list, V, E, src, dst)
    
    prev_list = []
    prev_e = dst

    while prev_e != src:
        prev_list.append(prev[prev_e])
        prev_e = prev[prev_e][0]

    prev_list.reverse()
    
    for i in prev_list:
        print(*i)

if __name__ == "__main__":
    main()

 

2. 벨만 포드

다익스트라와 같은 최단 경로를 탐색하는 알고리즘이다. 하지만 다익스트라와의 차이점은 다익스트라는 음의 가중치가 없고 벨만 포드는 음의 가중치가 주어진다는 점이다. 해결 과정은 비슷하다. 벨만 포드의 경우 (정점의 수 - 1) 까지 탐색을 하고 이후 한번 더 탐색을 진행한다. 이 때 최단 거리가 갱신되는 값이 있으면 음의 루프가 존재한다는 의미이므로 문제에서 주어진 Negative Cycle!을 출력한다.

 

import heapq

def bellman_ford(v_dic, v_list, V, E, src, dst):
    INF = float('inf')
    distance = {}
    for i in v_list:
        distance[i] = INF
    distance[src] = 0
    predecessor = {}
    for i in v_list:
        predecessor[i] = None

    for i in range(V-1):
        for i in v_dic:
            for j, c in v_dic[i]:
                if distance[j] > distance[i] + c:
                    distance[j] = distance[i] + c
                    predecessor[j] = [i, j, c]
    
    for i in v_dic:
        for j, c in v_dic[i]:
            if distance[j] > distance[i] + c:
                return -1
    
    return predecessor

def main():
    V, E = map(int, input().split())
    v_list = input().split()
    v_dic = {}
    for i in v_list:
        v_dic[i] = []

    for _ in range(E):
        i, j, c = input().split()
        c = int(c)
        v_dic[i].append([j,c])

    src, dst = input().split()
    predecessor = bellman_ford(v_dic, v_list, V, E, src, dst)

    if predecessor == -1:
        print("Negative Cycle!")
    else:
        prev_list = []
        prev_e = dst

        while prev_e != src:
            prev_list.append(predecessor[prev_e])
            prev_e = predecessor[prev_e][0]

        prev_list.reverse()
    
        for i in prev_list:
         print(*i)

if __name__ == "__main__":
    main()

 

3. 경찰서

다익스트라를 활용한다. 시작 정점과 도착 정점을 (A, A) ~ (F, F)로 놓고 모든 경우를 탐색하고 이 값이 주어진 거리보다 작은 경우 새로운 dict형 변수에 저장한다. 이 과정이 종료되고 dict형 변수의 크기를 비교해서 이 값이 가장 큰 정점이 경찰이 다다를수 있는 지점이 가장 많은 정점이다.

 

import heapq

def dijkstra(v_dic, v_list, V, E, src, dst):
    INF = float('inf')
    distance = {}
    for i in range(V):
        distance[v_list[i]] = INF
    distance[src] = 0
    queue = []
    prev = {}
    for i in range(V):
        prev[v_list[i]] = []
    found = {}
    for i in range(V):
        found[v_list[i]] = False
    
    heapq.heappush(queue, [0, src])
    while queue:
        v = heapq.heappop(queue)
        found[v[1]] = True
        for node_weight in v_dic[v[1]]:
            if (found[node_weight[0]]):
                continue
            if (distance[node_weight[0]] > distance[v[1]] + node_weight[1]):
                distance[node_weight[0]] = distance[v[1]] + node_weight[1]
                heapq.heappush(queue, [distance[node_weight[0]], node_weight[0]])
                prev[node_weight[0]] = [v[1], node_weight[0], node_weight[1]]
    return distance[dst]

def main():
    V, E = map(int, input().split())
    v_list = input().split()
    v_dic = {}
    for i in v_list:
        v_dic[i] = []

    for _ in range(E):
        i, j, c = input().split()
        c = int(c)
        v_dic[i].append([j,c])
        v_dic[j].append([i,c])
    
    len_dic = {}
    for i in v_list:
        len_dic[i] = []

    min_len = int(input())

    for i in v_list:
        for j in v_list:
            result = dijkstra(v_dic, v_list, V, E, i, j)
            if min_len >= result:
                len_dic[i].append(result)
                len_dic[j].append(result)
    
    result = []
    
    for i in range(len(len_dic)):
        result.append([v_list[i],len_dic[v_list[i]]])
    result = sorted(result, key = lambda x : len(x[1]))
    print(result[len(result)-1][0], int(len(result[len(result)-1][1])//2))

if __name__ == "__main__":
    main()

 

- 깃허브 -

github.com/k906506/2020_Winter_Assemble-And-selfcode

 

k906506/2020_Winter_Assemble-And-selfcode

Contribute to k906506/2020_Winter_Assemble-And-selfcode development by creating an account on GitHub.

github.com

 

저작자표시

'⛹️ 라이프 > 2020 겨울방학 모각코(개인)' 카테고리의 다른 글

[코독하구만 팀] 2021.01.20(수) - 5주차 개인 결과  (0) 2021.01.22
[코독하구만 팀] 2021.01.20(수) - 5주차 개인 목표  (0) 2021.01.20
[코독하구만 팀] 2021.01.13(수) - 4주차 개인 결과  (0) 2021.01.13
[코독하구만 팀] 2021.01.13(수) - 4주차 개인 목표  (0) 2021.01.13
[코독하구만 팀] 2020.01.05(화) - 3주차 개인 결과  (0) 2021.01.05
[코독하구만 팀] 2021.01.05(화) - 3주차 개인 목표  (0) 2021.01.05
    '⛹️ 라이프/2020 겨울방학 모각코(개인)' 카테고리의 다른 글
    • [코독하구만 팀] 2021.01.20(수) - 5주차 개인 결과
    • [코독하구만 팀] 2021.01.20(수) - 5주차 개인 목표
    • [코독하구만 팀] 2021.01.13(수) - 4주차 개인 목표
    • [코독하구만 팀] 2020.01.05(화) - 3주차 개인 결과
    고도고도
    고도고도
    좋아하는 것을 하자\n 스위프트 찍먹중\n 광고 없는 블로그
    댓글쓰기
    다음 글
    [코독하구만 팀] 2021.01.20(수) - 5주차 개인 목표
    이전 글
    [코독하구만 팀] 2021.01.13(수) - 4주차 개인 목표
    • 이전
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • ···
    • 13
    • 다음