Algorithm-우주신과의 교감

in Algorithm, Graph, Kruskal

백준 5719 : 문제링크

  • 문제유형 :

    • 그래프
    • 크루스칼 알고리즘

  • 설명

    • 정점의 개수 N이 최대 1000이므로, 가능한 통로의 개수는 약 N^2이다
    • 크루스칼 알고리즘은 간선의 개수가 E일 때 O(ElogE)로 동작하므로 해결할 수 있다 (정렬 알고리즘 시간복잡도)

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    import math
    import sys

    input = sys.stdin.readline

    def get_distance(p1, p2):
        a = p1[0] - p2[0]
        b = p1[1] - p2[1]
        return math.sqrt((a * a) + (b * b))

    def get_parent(parent, n):
        if parent[n] == n:
            return n
        return get_parent(parent, parent[n])

    def union_parent(parent, a, b):
        a = get_parent(parent, a)
        b = get_parent(parent, b)
        if a < b:
            parent[b] = a
        else:
            parent[a] = b

    def find_parent(parent, a, b):
        a = get_parent(parent, a)
        b = get_parent(parent, b)
        if a == b:
            return True
        else:
            return False

    edges = []
    parent = {}
    locations = []
    n, m = map(int, input().split())

    for _ in range(n):
        x, y = map(int, input().split())
        locations.append((x, y))

    length = len(locations)

    for i in range(length - 1)
        for j in range(i + 1, length):
            edges.append((i + 1, j + 1), get_distance(location[i], location[j]))
        
    for i in range(1, n + 1):
        parent[i] = i

    for i in range(m):
        a, b = map(int, input().split())
        union_parent(parent, a, b)

    edges.sort(key=lambda data: data[2])

    result = 0
    for a, b, cost in edges:
        if not find_parent(parent, a, b):
            union_parent(parent, a, b)
            result += cost

    print("%0.2f" %result)

Comment and share

Algorithm-거의 최단 경로

in Algorithm, Graph, Dijkstra

백준 5719 : 문제링크

  • 문제유형 :

    • 그래프
    • 다익스트라 최단 경로 알고리즘

  • 설명

    • 다익스트라 최단 경로에 포함되는 모든 간선을 추적한다
    • 최단 경로에 포함되는 모든 간선을 추적할 때 DFS를 사용하여 추적하여 제외시킨다
    • 제외된 간선 외에서 다익스트라 최단 경로 알고리즘으로 차선 최단 경로를 찾는다

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    from collections import deque
    import heapq
    import sys

    input = sys.stdin.readline

    def dijkstra():
        heap_data = []
        heapq.heappush(heap_data, (0, start))
        distance[start] = 0
        while heap_data:
            dist, now = heapq.heappop(heap_data)
            if distance[now] < dist:
                continue
            for i in adj[now]:
                cost = dist + i[1]
                if distance[i[0]] > cost and not dropped[now][i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(heap_data, (cost, i[0]))

    def bfs():
        q = deque()
        q.append(end)
        while q:
            now = q.popleft()
            if now == start:
                continue
            for prev, cost in reverse_adj[now]:
                if distance[now] == distance[prev] + cost
                    dropped[prev][now] = True
                    q.append(prev)

    while True:
        n, m = map(int, input().split())
        if n == 0:
            break
        start, end = map(int, input().split())
        adj = [[] for _ in range(n + 1)]
        reverse_adj = [[] for _ in range(n + 1)]
        for _ in range(m):
            x, y, cost = map(int, input().split())
            adj[x].append((y, cost))
            reverse_adj[y].append((x, cost))
        dropped = [[False] * (n + 1) for _ in range(n + 1)]
        distance = [1e9] * (n + 1)
        dijkstra()
        bfs()
        distance = [1e9] * (n + 1)
        dijkstra()
        if distance[end] != 1e9:
            print(distance[end])
        else:
            print(-1)

Comment and share

Algorithm-해킹

in Algorithm, Graph, Dijkstra

백준 10282 : 문제링크

  • 문제유형 :

    • 그래프
    • 다익스트라 최단 경로 알고리즘

  • 설명

    • 정점의 개수 N, 간선의 개수 D
    • 우선순위 큐를 이용하여, 시간복잡도 O(NlogD)로 해결할 수 있습니다

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    import heapq
    import sys
    input = sys.stdin.readline

    def dijkstra(strat):
        heap_data = []
        heapq.heappush(heap_data, (0, start))
        distance[start] = 0
        while heap_data:
            dist, now = heapq.heappop(heap_data)
            if distance[now] < dist:
                continue
            for i in adj[now]:
                cost = dist + i[1]
                if distance[i[0]] > cost:
                    distance[i[0]] = cost
                    heapq.heappush(heap_data, (cost, i[0]))

    for _ in range(int(input())):
        n, m, start = map(int, input().split())
        adj = [[] for i in range(n + 1)]
        distance = [1e9] * (n + 1)
        for _ in range(m):
            x, y, cost = map(int, input().split())
            adj[y].append((x, cost))
        dijkstra(start)
        count = 0
        max_distance = 0
        for i in distance:
            if i != 1e9:
                count += 1
                if i > max_distance:
                    max_distance = i
        print(count, max_distance)

Comment and share

Algorithm-효율적인 해킹

in Algorithm, Graph, BFS

백준 1325 : 문제링크

  • 문제유형 :

    • 그래프 탐색

    • BFS

  • 설명

    • DFS, BFS를 수행할 때마다 방문하게 되는 노드의 개수를 계산
    • 가장 노드의 개수가 크게 되는 시작 정점을 출력

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    from collections import deque

    n, m = map(int, input().split())
    adj = [[] for _ in range(n + 1)]

    for _ in range(m):
        x, y = map(int, input().split())
        adj[y].append(x)

    def bfs(v):
        q = deque([v])
        visited = [False] * (n + 1)
        visited[v] = True
        count = 1
        while q:
            v = q.popleft()
            for e in adj[v]:
                if not visited[e]:
                    q.append(e)
                    visited[e] = True
                    count += 1
        return count

    result = []
    max_value = -1

    for i in range(1, n + 1):
    c = bfs(i)
    if c > max_value:
        result = [i]
        max_value = c
    elif c == max_value:
        result.append(i)
        max_value = c

    for e in result:
        print(e, end = " ")

Comment and share

Algorithm-유기농 배추

in Algorithm, Graph, DFS

백준 1012 : 문제링크

  • 문제유형 :

    • 그래프 탐색

    • DFS

  • 설명

    • 연결 요소의 개수를 세는 문제
    • 모든 정점에 대하여 BFS를 수행하고, 한 번 방문한 정점은 다시 확인하지 않음
    • BFS를 수행한 총 횟수를 계산

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    import sys
    sys.setrecursionlimit(100000)

    def dfs(x, y):
        visited[x][y] = True
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if nx < 0 or nx >= n or ny < 0 or ny > m:
                continue
            if array[nx][ny] and not visited[nx][ny]:
                dfs(nx, ny)

    for _ in range(int(input())):
        m, n, k = map(int, input().split())
        array = [[0] * m for _ in range(n)]
        visited = [[False] * m for _ in range(n)]
        for _ in range(k):
            y, x = map(int, input().split())
            array[x][y] = 1
        result = 0
        for i in range(n):
            for j in range(m):
                if array[i][j] and not visited[i][j]:
                    dfs(i, j)
                    result += 1
        print(result)

Comment and share

Algorithm-바이러스

in Algorithm, Graph, DFS

백준 2606 : 문제링크

  • 문제유형 :

    • 그래프 탐색

    • DFS

  • 설명

    • 시작 정점에서부터 도달할 수 있는 노드의 수를 계산

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    n = int(input())
    m = int(input())
    adj = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)
    count = 0

    for _ in range(m):
        x, y = map(int, input().split())
        adj[x].append(y)
        adj[y].append(X)

    def dfs(now_pos):
        global count
        count += 1
        visited[now_pos] = True
        for next_pos in adj[now_pos]:
            if not visited[next_pos]:
                dfs(next_pos)

    dfs(1)
    print(count - 1)

Comment and share

Algorithm-숨박꼭질

in Algorithm, Graph, BFS

백준 1697 : 문제링크

  • 문제유형 :

    • 그래프 탐색

    • BFS

  • 설명

    • 특정 위치까지 이동하는 최단 시간을 계산
    • 이동 시간이 모두 1초로 동일, BFS를 이용하여 해결

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    from collections import deque

    MAX = 100001
    n, k = map(int, input().split())
    array = [0] * MAX

    def bfs():
        q = deque([n])
        while q:
            now_pos = q.popleft()
            if now_pos == k:
                return array[now_post]
            for next_pos in (now_pos - 1, now_pos + 1, now_pos * 2):
                if 0 <= next_pos < MAX and not array[next_pos]:
                    array[next_pos] = array[now_pos] + 1
                    q.append(next_pos)

    print(bfs())

Comment and share

Algorithm-DFS와 BFS

in Algorithm, Graph

백준 1260 : 문제링크

  • 문제유형 :

    • 그래프 탐색

    • BFS DFS

  • 설명

    • 정점 번호가 작은것부터 방문
    • 모든 노드와 모든 간선을 차례대로 조회하여 O(N + M)의 시간 복잡도

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    from collections import deque

    def dfs(v):
        print(v, end = ' ')
        visited[v] = True
        for e in adj[v]:
            if not(visted[e])
                dfs(e)

    def bfs(v):
        q = deque([v])
        while q:
            v = q.popleft()
            if not(visited[v]):
                visited[v] = True
                print(v, end = ' ')
                for e in adj[v]:
                    if not visited[v]:
                        q.append(e)

    n, m, v = map(int, input().split())
    adj = [[] for _ in range(n + 1)]

    for _ in range(m):
        x, y = map(int, input().split())
        adj[x].append(y)
        adj[y].append(x)

    for e in adj:
        e.sort()

    visited = [False] * (n + 1)
    dfs(v)
    print()
    visited = [False] * (n + 1)
    bfs(v)

Comment and share

  • page 1 of 1

Yechan Kim

author.bio


author.job