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

Algorithm-중량제한

in Algorithm, Search, Binary Search

백준 1939 : 문제링크

  • 문제유형 :

    • 탐색

    • 이진탐색

    • BFS

  • 설명

    • 다리의 개수 M의 최대 100,000, 중량 제한 C는 최대 1,000,000,000

    • 이진탐색을 이용하면 시간 복잡도는 O(M * logC)

    • 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
    from collections import deque

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

    def bfs(c):
        queue = deque([start_node])
        visited = [False] * (n + 1)
        visited[start_node] = True
        while queue:
            x = queue.popleft()
            for y, weight in adj[x]:
                if not visited[y] and weight >= c:
                    visited[y] = True
                    queue.append(y)
        return visited[end_node]

    start = 1000000000
    end = 1

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

    start_node, end_node = map(int, input().split())

    result = start
    while(start <= end):
        mid = (start + end) // 2
        if bfs(mid):
            result = mid
            start = mid + 1
        else:
            end = mid - 1

    print(result)

Comment and share

  • page 1 of 1

Yechan Kim

author.bio


author.job