0. 서문

최근 알고리즘 공부를 하면서 생각한건데 풀기만 하고 정리를 안하다보니 비슷한 문제를 풀때 고생을 하는 경우가 많은것같아서 하루동안 풀었던것도 정리하고 그날 있던일들도 조금씩 정리를 해볼까 한다.

1. 아침산책

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

개인적으로 문제를 처음 보자마자 든 생각은 실외를 기준으로 계산을 해야한다는 것이었는데 솔직히 그냥 감으로 찍어본거라 이 생각이 맞는지 그리고 실외를 기준으로 한다고 하더라도 코드를 어떻게 짜야할지 의사코드 조차 짜기 힘들었던 문제였다.

DFS 를 통해 풀어야 한다는 것은 분류를 통해서 알았기에 기본 틀정도는 짜었으나 솔직히 딱 거기까지. 그 이상은 혼자서 고민해도 도저히 답이 안나와서 결국 찾아보게되었다.

https://kth990303.tistory.com/141

https://woonys.tistory.com/entry/정글사관학교-22일차-TIL-아침-산책with-Python-위상-정렬-알고리즘

문제를 푸는 방법은 실외노드를 기준으로 두고 인접한 실내노드의 갯수를 새는것이 중심이었다. 추가로 노드를 정리하는 과정에서 이어진 노드가 서로 실내노드라면 노드의 순서가 달라지면 다른 경로로 취급하기 때문에 경로의 수에 +2 를 해주는것 까지가 중요한 점이었다.

해당하는 문제를 풀면서 느낀점은 솔직히 문제에 대한 파악 능력이 상당히 떨어지지 않나 라는 점 그리고 해당 문제를 풀 시기에 DFS 문제들은 어느정도 파악하고 풀 수 있다고 생각했는데 지극히 개인적인 착각이라는것도 깨닫게 되었다. 아마, 이번 주차가 끝나기 전까지 DFS, BFS 문제들을 풀 수 있을만큼은 최대한 더 풀어야겠다는 생각이 들어다.

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline


def dfs(start, value):
    visited[start] = True
    for i in graph[start]:
        if location[i] == 1:
            value += 1
        elif not visited[i] and location[i] == 0:
            value = dfs(i, value)
    return value


n = int(input())
graph = [[] for _ in range(n+1)]
visited = [False]*(n+1)
location = [0]+list(map(int, input().strip()))
cnt = 0

for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

    if location[a] == 1 and location[b] == 1:
        cnt += 2

hap = 0
for i in range(1, n+1):
    if not visited[i] and location[i] == 0:
        x = dfs(i, 0)
        hap += x*(x-1)

print(cnt + hap)

2. 최소비용 구하기

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

다익스트라 알고리즘을 통해 풀어야 하는 문제였다.
해당하는 알고리즘에 대한 부분은 나동빈 님의 강의를 통해서 배우게 되었다.

https://youtu.be/611B-9zk2o4

최소비용 구하기 와 같은 유형의 문제는 앞으로도 많이 나올것같기에 이번기회에 제대로 알아두면 좋을것같다는 생각은 들었으나 솔직히 한번만으로 이해하기는 쉽지않아 여러번 비슷한 문제들을 풀고 영상도 반복해서 보는수밖에 없지 않나 하는 생각이 들었다.

다익스트라 알고리즘의 경우 heapq 를 통해 구현할 경우 시간복잡도가 O(ElogV) 지만 쓰지 않을경우 O(V^2) 가 되어 시간복잡도에서 차이가 많이 나기 때문에 heapq 를 써서 구현하는 쪽으로 하게 되었다.

from heapq import heappush, heappop
import sys
input = sys.stdin.readline
infinity = int(2e9)


def Dijkstra(start):
    dp[start] = 0
    heap = []
    heappush(heap, [0, start])

    while heap:
        w, n = heappop(heap)
        if dp[n] < w:
            continue
        for x, y in arr[n]:
            z = w + y
            if dp[x] > z:
                dp[x] = z
                heappush(heap, [z, x])


n = int(input())
m = int(input())
arr = [[] for _ in range(n+1)]
dp = [infinity for i in range(n+1)]

for i in range(m):
    start_p, end_p, cost = map(int, input().split())
    arr[start_p].append([end_p, cost])

start, end = map(int, input().split())

Dijkstra(start)
print(dp[end])

근데 솔직히 하게 되었다고 뭐고 이쪽도 결국 답을 찾아보게 되버려서...나중에 다시 풀어봐야지.