Graph

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이다. 예를 들어

문제 시간 제한: 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