[SW정글] Week 03 개발일지

 

Week 03 개발일지

그래프 탐색 기본

• preorder, inorder, postorder 순회(traversal)
• 최소 비용 신장 트리(Minimum Spanning Tree)
  • 트리에서 모든 노드를 방문하는 최소 비용
  Prim Kruskal

  기준	Vertex	Edge
  이동	방문한 Node에서 이어져나감	전체가 이어져있지 않은 Edge에서도 가능
  제한	전체가 연결되어있는 Graph에서만 가능	나눠져있는 Graph에서도 가능
  시간	정렬 여부에 따라 O(E log v) ~ O(v^2)	항상 O(E log v)

  • Kruskal
    • 매번 최소 edge를 선택해서 트리 형성
    • edge 선택으로 트리가 합쳐질 때 Find-Union 사용
  • Prim
    • 어떤 한 node에서 시작
    • node에서 아직 방문하지 않은 다른 node로 가는 edge들을 저장
    • 저장된 edge 중에서 최소 edge 선택하고 node 이동
    • 이 후 반복
• 연결 요소(Connected Component)
  • 주어진 조건의 그래프에서 연결된 부분 그래프

Depth First Search

• 깊이 우선 탐색
• 이분 그래프
  • 모든 vertex를 빨강과 파랑으로 색칠하되, 모든 edge가 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프
  • 그래프의 꼭짓점들을 깊이 우선 탐색으로 나열한 뒤, 각 꼭짓점들을 이웃 꼭짓점들과 다른 색으로 계속해서 칠해 나가면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 여부를 확인하면 된다. 시간 복잡도는 O(|V|+|E|)이다.

Breadth First Search

• 넓이 우선 탐색
• 다익스트라 알고리즘(Dijkstra Algorithm)
  • 음의 가중치가 없는 Graph의 한 Vertex에서 모든 Vertex까지의 최단거리를 각각 구하는 알고리즘
  • 시간 복잡도 O((V+E)logV) (V는 Vertex 개수, E는 한 Vertex의 주변 Vertex)
    • 각 Vertex마다 미방문 Vertex 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 Vertex를 찾는데 O(VlogV)
    • 각 Vertex마다 이웃한 노드의 최단 거리를 갱신할 때 O(ElogV)
  • 알고리즘 과정
    1. 출발점부터 각 Vertex까지 최단거리가 저장되는 배열을 만들고 출발점은 0, 나머지는 매우 큰 값(갈 수 없음을 의미)으로 채워 넣는다.
    2. 최단거리를 기준으로 하는 최소 힙트리에 출발점의 최단거리와 출발점을 push
    3. 최소 힙트리에서 pop한다 → 현재 위치한 Vertex
    4. 현재 계산 중인 가중치가 현재 Vertex의 최단거리 배열에 저장된 값보다 크면 스킵
    5. 현재 Vertex에서 갈 수 있는 Vertex와 가중치 값을 살펴본다
    6. 현재 계산 중인 가중치에 다음 Vertex로 가는데 필요한 가중치의 합이 최단거리 배열에 저장된 값보다 작으면 교체
    7. 갱신된 최소비용과 다음 Vertex를 최소 힙트리에 push
    8. 3 ~ 7 과정을 최소 힙트리가 빌 때까지 반복한다.
    9. 최단거리 배열 완성
  • 관련 알고리즘
    • 벨만-포드 알고리즘
      • 다익스트라 알고리즘과 목표와 같지만 일반적으로 느리다
      • 음수 사이클이 없을 경우 음수 가중치가 있어도 사용가능하다
    • 플로이드-워셜 알고리즘
      • Graph에서 가능한 모든 Vertex 쌍에 대해 최단 거리를 구하는 알고리즘
      • 시간복잡도 O(V^3)
      • 음의 가중치를 가지는 그래프에도 사용할 수 있다
    • A* 알고리즘
      • 가중치를 계산할 때 다익스트라 알고리즘에 heuristic 함수(h(x))을 추가하여 만든 경로 탐색 알고리즘
      • h(x)에 따라 성능이 갈림

위상 정렬

• 여러 일들에 순서가 정해져 있을 때 순서에 맞게끔 나열하는 것
• 위상정렬 조건
  • Graph에 Cycle이 있으면 안된다.
  • 방향 Graph
• 위상정렬 과정
  1. 진입차수가 0인 Vertex와 그 Vertex와 연결된 Edge를 모두 지운다
  2. 남아있는 Vertex의 진입차수를 갱신한다
  3. Graph의 모든 Vertex가 없어질 때까지 1 ~ 2의 과정을 반복한다

Test

2667번: 단지번호붙이기

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
arr = [list(map(int, list(input().strip()))) for x in range(n)]


def solution(arr):
    def dfs(start):
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]

        que = [start]
        cnt = 0

        while que:
            cur_v = que.pop()
            x, y = cur_v

            if arr[x][y] == 0:
                continue
            arr[x][y] = 0
            cnt += 1

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] == 1:
                    que.append((nx, ny))

        return cnt

    result = 0
    house = []
    for i in range(n):
        for j in range(n):
            if arr[i][j]:
                result += 1
                house.append(dfs((i, j)))

    return result, house


result, house = solution(arr)
print(result)
for temp in sorted(house):
    print(temp)

18405번: 경쟁적 전염

import sys
from collections import deque
from heapq import *

input = sys.stdin.readline

n, k = map(int, input().split())
arr = [list(map(int, input().split())) for x in range(n)]
s, tx, ty = map(int, input().split())


def virus(arr, k):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    heap = []

    for i in range(n):
        for j in range(n):
            if arr[i][j]:
                heappush(heap, [0, arr[i][j], i, j])
                arr[i][j] = 0

    while heap:
        t, vi, x, y = heappop(heap)

        if t == s + 1:
            break

        if arr[x][y]:
            continue
        arr[x][y] = vi

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] == 0:
                if not arr[nx][ny]:
                    heappush(heap, [t + 1, vi, nx, ny])

    return arr[tx - 1][ty - 1]


print(virus(arr, k))

1939번: 중량제한

import sys
from heapq import *

input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for x in range(m)]
f1, f2 = map(int, input().split())

graph = [[] for x in range(n + 1)]
for v1, v2, w in arr:
    graph[v2].append((v1, w))
    graph[v1].append((v2, w))

for i in range(1, n + 1):
    graph[i].sort(key=lambda x: (x[0], -x[1]))

weight = [0] * (n + 1)


def limit_weight(f1, f2):
    weight[f1] = -2e9
    heap = [[weight[f1], f1]]

    while heap:
        cur_w, cur_v = heappop(heap)
        cur_w = -cur_w

        if cur_v == f2:
            break

        if cur_w < weight[cur_v]:
            continue

        for next_v, next_w in graph[cur_v]:
            temp_w = min(cur_w, next_w)

            if weight[next_v] < temp_w:
                weight[next_v] = temp_w
                heappush(heap, [-temp_w, next_v])


limit_weight(f1, f2)
print(weight[f2])

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for x in range(m)]
f1, f2 = map(int, input().split())


def limit_weight(f1, f2):
    graph = [[] for x in range(n + 1)]
    for v1, v2, w in arr:
        graph[v1].append((v2, w))
        graph[v2].append((v1, w))

    def dfs(f1, f2, weight):
        visited = [False] * (n + 1)
        que = deque([f1])

        while que:
            cur_v = que.popleft()

            if cur_v == f2:
                return True

            if visited[cur_v]:
                continue
            visited[cur_v] = True

            for next_v, next_w in graph[cur_v]:
                if not visited[next_v] and next_w >= weight:
                    que.append(next_v)

        return False

    start = 1
    end = 1e9
    result = -1

    while start <= end:
        mid = int((start + end) // 2)

        if dfs(f1, f2, mid):
            start = mid + 1
            result = mid

        else:
            end = mid - 1

    return result


print(limit_weight(f1, f2))