Graph

Graph and representationsBFSDFSBFS vs DFSin Directed Graphin Undirected GraphDijkstraBellman-FordFloyd Warshall...Prim's MSTKruskal's MSTStackkahn's A

Vertices(Nodes)와 Edges로 이루어진 Data Structure, G( V, E )다음은, Undirected Graph의 예시이다.다음의 두 가지 방법으로 그래프를 표현할 수 있다.1) Adjacency Matrix2) Adjacency ListVxV

Graph를 Depth First Search 하면 하나의 Tree를 만들 수 있다. 이때, 이 Tree에 back edge가 존재하면, Cycle이 있다고 말한다Tree에서 Back Edge(https://en.wikipedia.org/wiki/Depth-f

weighted graph가 주어졌을 때, 하나의 src vertex에서 다른 모든 vertices로 가는 최소 비용을 구하는 알고리즘pseudo-code

Topological Sorting은 여러 가지 일들에 순서가 있을 때, 그 순서를 거스르지 않도록 일을 나열하는 것을 말한다. 각 일들을 nodes로 보면 일종의 Directed Graph로 볼 수 있다. 이때, Cycle이 있다면 순서를 거스르지 않는 것이 불가능

Directed Graph의 모든 정점이 다른 모든 정점에 도달 가능한 경우, "Strongly Connected" 라고 한다. Strongly Connected Components(SCC)는 가장 큰 strongly connected subgraph이다. 예를 들어

서로소 집합을 관리하는 데 사용하는 자료구조이다.집합을 나타내기 위해선, 각 집합마다 대표자(parent)를 사용한다.이 p가 집합을 확인하고 추가하는 핵심 요소이다.parents\[]에 각 노드의 parent(집합 대표자)를 저장한다.이를 통해 어느 집합에 속해있는

MST > A minimum spanning tree (MST) is defined as a spanning tree that has the minimum weight among all the possible spanning trees. > A spanning tre

문제 시간 제한: 1초 메모리 제한: 256MB Problem Analysis 인접한 nodes로 퍼지게 하면된다. BFS 알고리즘을 사용하면 된다. Algorithm BFS 알고리즘으로 다음 날짜에 익을 토마토들을 queue에 추가한다. Data Structu

시간 제한: 2초메모리 제한: 512MB각 거리에 있는 칸을 모두 조사하여, 먹을 수 있는 최적의 물고기가 있는지 찾으면 된다. BFS를 사용하면, 인접한 칸을 가까운 곳부터 먼 곳까지 점차적으로 조사할 수 있다.BFS를 사용하여, 점차적으로 먼 칸을 조사먹이를 발견하

문제 시간 제한: 2초 메모리 제한: 256MB Problem Analysis 한 node에 연결된 다른 모든 nodes를 반대 집합에 포함시키면서 순회하면 된다. 이때, 같은 집합으로 연결된다면 Bipartite Graph가 아니다. Algorithm Data

시간 제한: 6초메모리 제한: 256MB최적의 방법으로, 모든 가능한 경우를 조사해야 한다. 재귀로 쪼개서 풀면, 한쪽으로만 깊게 들어갈 수 있다. 대신, BFS를 이용하여, 같은 level의 것들을 모두 조사하고 다음 level로 넘어가는 방식을 취하면 된다.BFS

시간 제한: 1초 메모리 제한: 128MB특정 칸에서 순회를 시작하여 방문하게 되는 모든 칸들은 같은 구역이고, 방문하지 않으면 다른 구역이다. 순회를 했을 때 서로 접근할 수 없는 구역의 개수를 세면 된다. 이때, 넓이든 깊이든 모든 칸을 순회만 할 수 있으면 되기

시간 제한: 1초메모리 제한: 512MB주사위를 한번 던졌을 때 갈 수 있는 칸, 두 번 던졌을 때 갈 수 있는 칸, 그다음으로 갈 수 있는 칸을 순차적으로 조사하며 도착할 때까지 시도해야 한다. 따라서, BFS 알고리즘이 적합해 보인다.1번 칸을 Queue에 넣는다.

시간 제한: 3초메모리 제한: 256MB싸이클에 포함되면 같은 팀이고, 싸이클에 포함되지 못하면 팀이 아니다. 싸이클을 찾는 것이 문제의 핵심이다. Depth First Search를 통해 stack에 올려져 있는 node에 방문하는지 확인하면서 Cycle을 찾으면 된

시간 제한: 2초메모리 제한: 256MB최적의 경로를 선택할 수 있는 규칙은 따로 없고, 가능한 경우를 모두 조사하는 수밖에 없다. 현재까지의 경로를 함께 저장하며, 순회하면 된다.이때, 같은 k 거리의 칸이라도 지나온 경로에 따라 다른 경우가 되기 때문에, BFS를

문제 시간 제한: 1초 메모리 제한: 128MB Problem Analsysis 문제의 핵심은

시간 제한: 2초메모리 제한: 512MB두 nodes u, v 사이 최단 경로에 4개 이상의 edge가 존재하는지 확인하는 것이 문제의 목표이다. DFS로 확인하면 된다. 그러나 아래의 경우처럼, 파란색으로 가면 네 번 거치지만, 빨간색으로 가면 세 번 거친다. 따라서

시간 제한: 2초메모리 제한: 128MBA가 나온 이후에 B가 다음으로 나와야 한다. 이는 node A에서 node B로 가는 edge로 볼 수 있다. 또한, a->b->c->a 형태는 나올 수 없기 때문에, Cycle이 존재하지 않는다. 따라서, 일종의 Directe

시간 제한: 2초메모리 제한: 128MB문제 간의 정해진 순서를 거스르지 않고 정렬해야 한다는 점에서 Topological Sorting 문제이다. 그런데, 문제를 풀 때마다, 앞으로 풀 수 있는 문제의 pool이 달라지는데, 그때마다 가장 쉬운 문제를 풀어야 한다.

시간 제한: 2초메모리 제한: 512MBNaive 하게 DFS로 모든 경우의 수를 조사하면 만나는 시간을 구하는 데만 O( V\*(V+E) )이다. 이는, 시작 지점에서 도시 u로 가는 시간을 새로 갱신하면, u와 인접한 도시들도 다시 갱신해 주어야 하기 때문에 발생하

시간 제한: 1초메모리 제한: 256MB이러한 상황이 있을 때, 빨간색으로 체크한 부분을 넘어뜨려야 한다. Topological Order 순으로 넘어뜨리면 된다.Topological Sort를 한다.Topological order를 하나씩 pop하면서, 넘어지지 않은

시간 제한: 1초메모리 제한: 256MB이러한 경우에는 0, 1, 2 에서 시작하면 모든 구역에 도달할 수 있고,이러한 경우에는 모든 구역에 도달할 수 있는 시작 지점이 없다.시작 지점을 제외한 다른 모든 구역은 최소한 어느 한 구역으로부터 접근 가능해야한다. 즉, S

시간 제한: 2초메모리 제한: 128MBu, v가 서로 도달할 수 있다면 SCC에 해당한다.SCC 마다 각각 최소 비용의 경찰서 하나를 지으면 된다.SCC 를 구한다.각 SCC 별로 최소 비용의 경찰서 하나씩을 찾아 합한다.GraphOther

문제 문제 분석 모든 학생은 2개의 선물을 받아야한다. 그런데 선물은 0, 1, 2, 3...개로 사람마다 다양하게 받을 수 있다. 이때 처음부터 2개 미만의 선물을 받는 사람은 가능성이 전혀 없다. 따라서, 2개 미만의 선물을 받는 사람을 제거해야 한다. 다음은 3

같은 도시를 여러 번 방문해도 되기 때문에 연결만 되있으면 여행 계획은 무조건 달성할 수 있다.따라서 여행 계획에 포함된 도시들이 연결된 상태인지를 확인하면 된다.그리고 이러한 set을 유지하기 위해서는 disjoint set이 적절할 것 같다.disjoint setO

Naive하게 풀면 어떻게 풀 수 있을까?빈 자리의 상하좌우중 하나를 택하여 자리를 바꿀 수 있는데, 가능한 모든 경우를 조사하면 된다.DFS로도 풀 수 있으나, 최단거리 이기 때문에 BFS를 써서 푸는 것이 좋겠다.다만, 보드판의 상태 방문 여부를 체크해줘야 무한 루

BFS로 풀면 된다.다만 하이퍼튜브라는 특이한 구조 때문에 adjList를 쉽게 구할 수 없다.따라서, station to hypertubes, hyptertube to stations 두 가지를 이용해서 이동하며, 각각에 대해서도 visited를 두면 되겠다.bfsq