그래프

[python3] 백준 1389 풀이 ( 케빈 베이컨의 6단계 법칙, 플로이드 워샬 )

이번 문제는 케빈 베이컨의 6단계 법칙이다. 케빈 베이컨이 할리우드의 핵 인싸라는 것을 인지하고 문제에 들어가자. 문제를 보자 문제가 상당히 길다. 읽어보면 그냥 네트워크 안에서 여러 사람들과 연결되어 있을때 모든 타인과 몇번만에 연결되어 있는지를 알아내어 최솟값을 가지는 즉, 허브 역할을 하는 사람을 구하면 된다. 문제를 잘 읽어보면 결국 N정점에서 N정점으로의 갈 때 얼마나 걸리는지를 구해야 한다. 그래야 한 노드에서 모든 노드에 방문할 때 케빈 베이컨의 수를 구할 수 있다. 즉, 모든 쌍 최단 거리 알고리즘을 사용하면 구할 수 있다. 모든 쌍 최단 거리 알고리즘의 대표적인 놈이 "플로이드 워샬"이다. 그러나! 플로이드 워샬은 O(N^3)이 걸리기 때문에 N값이 너무 크면 문제가 발생할 수 있다. 다..

[c++] 백준 11657 풀이 ( 타임머신, 최단경로, 벨만-포드, 음수 가중치 )

우선 이 문제를 풀기위해서는 벨만-포드 알고리즘을 이해해야한다. 벨만-포드 단일시작점 알고리즘 (출발 노드가 고정) 최단 경로 알고리즘 음수 간선 가능 음수 사이클 확인 가능 쓱 보면 다익스트라와 비슷해보인다.(https://guccin.tistory.com/112?category=977502) 그러나 다익스트라와 달리 벨만-포드 알고리즘은 음수 간선에 대해서 최단거리를 알아낼수 있다. 또한 다익스트라는 우선순위 큐를 활용하여 최단 경로를 구하는데에 반해 벨만-포드는 매번 모든 간선을 전부 확인하며 최단거리를 알아내기 때문에 다익스트라보다 시간복잡도가 크다. 다익스트라 O(|E||log|V|), 벨만-포드 O(|E||V|) [c++] 백준 1753 풀이 ( 최단 경로, 다익스트라, 그래프, 우선순위 ) ..

[c++] 백준 1753 풀이 ( 최단 경로, 다익스트라, 그래프, 우선순위 )

다익스트라 다익스트라는 다이나믹 프로그래밍을 활용한 최단경로 탐색 알고리즘이다. 단일 시작점 알고리즘에 속하여 시작점을 기준으로 각 노드까지의 최단 거리를 알 수 있다. 이때 시간 복잡도를 줄이기 위해 우선순위 큐를 활용하면 좋다. 음수 간선이 없을때 사용 (음수가 있으면 벨만-포드나 플로이드를 사용하는게 좋다) 우선순위 큐를 활용 단일 시작점 알고리즘 다익스트라 알고리즘은 BFS처럼 동작한다. 시작점에서부터 BFS탐색을 진행한다. 단, 우선순위 큐에서 노드를 뽑을때는 간선의 가중치가 가장 낮은 노드를 뽑는다.(우선순위 큐에 {-가중치,노드} 형태로 넣으면 된다.) 해당 노드와 접한 노드를 뽑아서 dp에 최단경로를 메모이제이션한다. 이후 최단경로 가중치를 노드와 함께 큐에 넣고 루프를 돌며 반복한다. 문..

[c++] 백준 1197 풀이 (MST, 최소 신장 트리, 그래프, 유니온 파인드)

이번에는 MST를 풀어보자. MST는 Minimum Spanning Tree의 약자로 span이란 기간을 의미해서 직역하면 최소화된 기간 트리이다. 좀 더 풀어 말하면 트리가 낮은 가중치로 연결되어 있다고 볼 수 있다. 다르게는 그래프의 최소 연결 부분 그래프 라고 할 수 있다. 이번 문제를 풀기 위해서는 MST를 알기 이전에 Spanning Tree에 대해서 이해해야한다. Spanning Tree 간선 수가 가장 작게 연결된다. 만약 정점이 V개라면 V-1개로 연결된 트리 사이클이 존재하지 않는다.(트리의 형태) Minimum Spanning Tree 값이 가장 작은 간선을 이용하여 만든 Spanning Tree 간선 가중치 합이 최소여야 한다. 사이클이 존재하지 않는다. 크루스칼 알고리즘과 프림알고리..

[c++] 백준 1717 풀이 (집합의 표현, 그래프, 서로소 집합, 유니온파인드)

서로서 집합은 상호 배타적 집합(Disjoint-set) 이라고 한다. 교집합이 공집합인 집합(서로소 집합) 들의 정보를 확인하고 조작할 수 있는 자료구조이다. - union : 두 노드를 한 그래프로 합친다. - find : 어떤 노드가 속한 집합을 반환 이 문제는 유니온 파인드를 이용하여 두 노드가 해당하는 집합을 합치거나 한 노드가 다른 노드의 집합에 속하는지 판별하는 문제이다. 따라서 union함수를 구현하고, find함수를 구현하여 풀이를 진행한다. 우선 find함수를 구현한다. find함수의 역할은 해당 노드의 부모로 탐색을 진행한다. 따라서 루트 노드를 만나는 경우 반환을 진행하며, 루트 노드가 아닌 경우에는 해당 노드의 부모에 루트 노드 값을 입력해준다. (즉 find과정을 통해 tree를..

백준 2583 파이썬 풀이 (영역 구하기, DFS)

이번 문제는 주어진 좌표만큼 색칠된 경우 색칠되지 않은 영역의 넓이와 개수를 구하면 된다. 1. 좌표를 배열위치로 바꾸기 2. DFS로 탐색하면서 넓이 구하기 이 두가지만 하면된다. 좌표는 그림을 그려서 구해보면 쉽게 확인가능하다. start = [(m-1-b),(0+a)] end = [(m-d),(c-1)] 로 바꾸면 된다. 그럼 DFS로 탐색하는 코드만 추가해주면 끝이다. m,n,k = map(int, input().split()) Map = [[0 for i in range(n)] for i in range(m)] for _ in range(k): a,b,c,d = map(int, input().split()) start = [(m-1-b),(0+a)] end = [(m-d),(c-1)] for i..

백준 1707 python 풀이 (이분 그래프, BFS)

일단 처음에 문제를 읽고는 생각보다 쉽다고 느꼈다. 단순히 BFS로 탐색하면서 이전 값이랑 비교하면 되겠구만 했다. 그런데 구현하는데 상당히 애를 먹었고, 시간초과가 떠서 오랜 삽질 중이다. 우선 시간초과 코드는 아래와 같다. from collections import deque import sys input = sys.stdin.readline T = int(input()) def BFS(v,e,color, d,q): color[q[0]] = 1 visited = [0 for i in range(v+1)] while q: target = q.popleft() visited[target] = 1 targets = d[target] for t in targets: if visited[t] == 0: q.a..

백준 7569 토마토 (BFS, 3차원)

이번 문제는 저번 7576문제를 3차원으로 바꾼 문제이다. https://guccin.tistory.com/92 백준 7576 토마토 (BFS, 행렬 그래프, python) 이번 문제는 원리도 파악하고 간단히 풀수 있다고 생각하고 코딩을 진행했다. 모든 예를 통과하고 반례도 통과하며 잘 코딩했다고 생각했으나 시간초과의 벽을 넘지 못하고 고수들의 코드를 보 guccin.tistory.com 조건은 똑같다. 하루마다 양 사이드의 토마토가 익어가는데 추가되는 조건은 위아래 상자도 같이 적용된다는 것이다. 대충 3차원으로 생각해보고 위아래 같이 익게하는 조건을 추가하면 끝이다. from collections import deque m,n,h = map(int, input().split()) #열 행 상자수 q ..