image.png 문제 파악 답이 될 수 있는 숫자를 구성하는 숫자가 정해져 있으므로, 답을 구성할 수 있는 숫자들을 그래프의 노드로 보고 BFS로 탐색하면서 최소가 되는 답을 찾을 수 있지 않을까 생각했다. 그러나 문제점은 이런 방식으로 탐색할 경우 답이 존재하지 않는 경우 종료하는 지점을 설정하는 것이 불가능 하다는 것이다. 문제 풀...

image.png 문제 파악 배열의 원소를 최소 횟수로 뒤집어 정렬된 배열을 만드는 문제이다. 배열의 최대 크기가 8이고 배열이 한 번 뒤집힐 때마다 다른 상태가 되며 정렬된 상태로 나아가야 된다는 점에서 착안해 배열의 현재 순서를 string으로 나타내 그래프의 노드로 표현하려고 했다. 이 과정에서 그래프의 순서를 뒤집는 경우의 수 를 따지면서...

BFS란 BFS 너비 우선 탐색이란 그래프의 탐색 알고리즘 중 한 가지이다. 너비 우선 탐색은 깊이 우선 탐색과 그래프 탐색 방식의 두 축을 이루는데, 깊이 우선 탐색이 더 이상 경로가 없을 때 까지 계속 한 방향으로 들어가는 것과 달리 시작점과 가까운 노드부터 탐색하는 방식이다. BFS의 구현 너비 우선 탐색 과정 중 새로운 노드를 발견하면 ...

문제 파악 image.png 그래프의 한 정점에서 인접한 정점끼리는 감시 카메라를 공유하는데, 이 때 모든 갤러리를 감시하는 감시 카메라의 최소 대수를 구하는 문제이다. 직관적으로 생각했을 때는 정점 별로 감시 카메라를 둔다고 가정했을 때 인접 정점들을 확인하면서 감시 카메라가 설치 되었는지 안되었는지를 체크 하면서 하나씩 늘려나가야 되는데 그 시작...

강결합 컴포넌트란 강연결 요소라고도 불리는 강결합 컴포넌트는 유향 그래프 내에서 정의되는 개념이다. 유향 그래프에서 두 정점 사이에서 양 쪽 모두 이동할 수 있는 경로가 존재하면 두 정점은 같은 강결합 컴포넌트(SCC)에 속해 있다고 말한다. 만약 같은 SCC에 속한 두 정점 중 한 정점이 또 다른 정점과 같은 SCC에 속해 있으면 세 정점간 오고 가는 ...

DFS를 통한 간선의 분류 DFS 스패닝 트리 깊이 우선 탐색을 수행하면 그 과정에서 그래프의 모든 간선을 최소 한 번씩은 만나게 된다. 그 중 처음 만나는 정점과 연결되는 간선은 따라가게 되는데, 이러한 간선들을 모아서 보면 트리 형태를 띠게 된다. 이러한 트리는 당연히, 모든 정점을 지나치므로 스패닝 트리가 되고 이를 DFS 스패닝 트리라고 ...

image.png 문제 파악 내가 생각한 접근법은 단어를 vertex로 보는 것이었다. 그러나 이렇게 그래프를 만든 뒤 오일러 서킷을 찾는 알고리즘을 실행시키면, 같은 단어를 두 번 사용하는 경우까지 따지게 되어 문제의 조건을 만족하지 못한다는 문제점이 생긴다. 그래서 해밀턴 경로를 찾는 알고리즘을 생각해 보았지만 해밀턴 경로를 찾는 알고리즘은 ...

오일러 서킷이란 오일러 서킷은 그래프의 각 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 말한다. 대표적인 오일러 서킷의 사례는 한 붓 그리기이다. 오일러 서킷이 존재하려면 각 간선이 모두 한 컴포넌트 안에 있어야 하고 ( 서로 연결될 수 없는 위치에 간선이 존재해서는 안된다) 각 vertex에 연결된 엣지의 수 가 짝수여야 한다. 만약 홀수...

문제 정의 특정 개수의 문자열을 받고, 그 정보를 바탕으로 알파벳 사전 순서를 결정하는 문제이다. 그래프와는 관련이 없어 보이는 문제이지만, 위상 정렬의 특성을 확인하면 문제를 해결할 수 있다. 위상 정렬은 의존성을 가진 그래프, 즉 순서를 가진 그래프를 순서에 모순이 생기지 않도록 정렬해 주는 특성을 가지고 있다. 알파벳 사전 순서를 예로 들면 d...