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, 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-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