Jonyo Programming

[BOJ 1956(G4)리뷰] 문제를 요약하면 사이클이 있는 경로 중 최단경로를 찾으면 된다. 시작점과 도착점을 특정한 상태에서 최단거리를 구할 수 없으므로, 플로이드-와샬 알고리즘을 통해 모든 노드 간의 최단거리를 구한다. 알고리즘을 수행한 후에 dist[i][j]는 i노드에서 j노드까지의 최단거리가 된다. 문제에서 사이클이 존재해야 한다고 했으므로 dist[i][j]와 dist[j][i]가 모두 존재해야 한다. 즉, 'i번 노드에서 j번노드까지의 최단거리 + j번 노드에서 i번 노드까지의 최단거리' 중 가장 작은값이 정답이 될 것이다. /* 21.02.05 BOJ : 1956 운동 (https://www.acmicpc.net/problem/1956) 플로이드-와샬 알고리즘 */ #include usi..

[BOJ 1865(G4)리뷰] 벨만포드 알고리즘을 이용하는 문제다. 시간이 되돌아 가는것 = 음의 가중치를 갖는 간선이라고 생각하면 된다. 도로는 양방향으로 이동이 가능하므로 양방향으로 입력을 받고, 웜홀은 단방향이므로 단방향으로 입력을 받는다. 그 후에 벨만포드 알고리즘을 수행하며 사이클이 있는지 확인하여 결과를 출력하면 된다. 나는 이 문제에서 두가지 실수를 했다. 첫째는 MAX값을 INT_MAX값으로 설정하여 거리를 갱신하는 부분에 오버플로우가 나 올바른 결과가 나오지 않았다. 둘째는 방문했던 적이 있던 정점에 대해서만 거리를 갱신하는 작업을 수행했었는데, 만약 시작노드가 다른 노드와 연결되어 있지 않은 노드라면, 나머지 노드는 거리를 갱신할 수 없게된다. 따라서 이 조건을 없애야 한다. 위 두가지..

[BOJ 10282(G4) 리뷰] 단순히 몇대의 컴퓨터가 감염되는지 구하는 문제가 아닌, 감염이 가능한 모든 컴퓨터가 감염되는 최단 시간을 구해야 한다. 그러므로 이 문제를 해결하기 위해서는 다익스트라 알고리즘을 사용해야 한다. 시작 컴퓨터가 주어졌으니 시작컴퓨터로부터 다익스트라 알고리즘을 수행한다. 그 후에 시간이 기록된 DIST배열 전체를 확인하여, 거리가 갱신된 노드들이 감염된 컴퓨터의 숫자가 된다. 그리고 감염이 되는 시간은 항상 0보다크므로 DIST배열중 가장 큰 값이 모든 컴퓨터가 감염되는 최단경로가 될 것이다. /* 21.02.02 BOJ : 10282 해킹 (https://www.acmicpc.net/problem/10282) 다익스트라 알고리즘 */ #include using namesp..

[BOJ 1854(P5) 리뷰] 다익스트라 알고리즘 + 우선순위 큐를 이용하여 풀었다. 다익스트라 알고리즘을 통해 1번노드부터 N번노드까지의 최단경로를 구할 수 있다. 이때, 최단경로만 저장하는 것이 아니라 가능한 모든 경로를 저장하면 된다. K번째 최단경로를 찾기위해 정렬된 모든 경로중 K번째에 있는 값을 출력하면 될것이라 생각했지만 그렇지 않았다. 가능한 모든 경로를 담을 수가 없기에 필요한 경로들만 담아야 한다. 이때 우선순위큐가 필요하다. 우선순위 큐를 내림차순으로 정렬한다면 큐의 SIZE가 K일때 큐의 TOP에 있는 값이 K번째로 큰값이라는것을 알 수 있다. 이 원리를 이용하면 된다. 새로운 경로가 계산될때마다 큐의 사이즈를 확인하여 큐에 넣는작업을한다. 큐의 사이즈가 K보다 작다면, 아직 K번..

[BOJ 1613(G3)리뷰] 플로이드-와셜을 이용한 알고리즘이다. 보통 모든 노드간의 최단거리를 구하는데 사용되지만 이러한 문제에도 응용할 수 있다. 결국 각각의 노드는 모든 노드에 대해 자신과 연결된 노드를 이용하여 노드간의 관계를 정의할 수 있냐 없냐로 나뉜다. 그리하여, 플로이드-와셜 알고리즘을 통하여 모든 연결을 확인하여 연결이 가능한 경우에만 배열에 기록하면 된다. 예를들어, "1 2"라는 입력은 1번사건이 2번사건보다 먼저 일어났다는 의미이다. 이후에 "2 3"이라는 입력이 있다면 1->2->3의 관계를 통해 1번사건이 3번사건보다 먼저 일어났다는것을 알 수 있다. 이렇게 알고리즘을 적용하고나면 연결여부를 기록한 배열에는 각각의 노드마다 자신보다 뒤에 일어난 사건의 번호들의 index를 가지..

[BOJ 9470(G3)리뷰] 처음에 문제 설명만 읽고는 문제를 이해하기 힘들었다. 결국은 위상정렬 문제인데 특별한 조건이 추가된 위상정렬이라고 생각하면 된다. 강이 시작하는 노드(들어오는 간선이 없는 경우)의 순서는 1번부터 시작한다. 입력은 "1 3"이런식으로 주어지는데 1번강에서 3번강으로 물이 흘러나간다는 소리이다. 이 때 들어오는 간선이 존재하는(3번노드) 노드의 정보는 자신에게 들어오는 노드 중 가장 큰 값의 크기에 따라 결정된다. 가장 큰 값이 2개 이상일 경우 이전 강의 값에 +1, 2개 미만일 경우는 이전 강의 정보를 그대로 가진다. 위 조건을 만족하기 위하여 별도의 배열을 만들었다. 해당 번호에 들어오는 물 중 가장 큰 값과, 그 갯수를 저장하는 코드를 추가했다. 나머지는 위상정렬 알고..

[BOJ 3860(P5)리뷰] 시작점부터 시작하여 목적지까지 도착해야 한다. 묘지가 있는곳으로는 이동할 수 없으며, 귀신 구멍이라는 특정한 칸으로 이동하면 다른 곳으로 시간을 워프하여 이동할 수 있다. 이때 시간을 과거로 되돌릴 수 있다. 인접한 칸을 간선으로 갖고, 귀신 구멍이라는 특별한 간선을 갖는 그래프라고 생각하면 된다. 다만, 과거로 되돌아 갈 수 있다고 했으니 음의 가중치를 갖는 그래프이다. 문제에서 최단거리를 구하라 했으니 최단거리를 구하는 알고리즘을 사용해야 한다. 시작지와 목적지가 주어져 있으므로 다익스트라 알고리즘이 적합하겠지만, 간선에 음의 가중치가 붙을 수 있으므로 벨만포드 알고리즘을 사용해야 한다. 만약 음의 사이클이 존재하면 "Never"를, 음의 사이클은 존재하지 않지만 목적지..

[BOJ 11438(P5)리뷰] 트리에서 두개의 정점이 주어졌을 때, 두 정점의 최소공통조상을 찾아야 한다. 최소 공통조상 이란 두개의 노드가 만나게 되는 부모 노드 중 가장 가까운 것을 말한다. 아래의 과정을 통해 구할 수 있다. dfs를 통해 모든 정점의 깊이를 기록하며 이때 자신의 위에있는 부모노드의 번호를 저장한다. 두개의 정점을 입력받고, 두 정점의 깊이를 맞춘다. 같아진 깊이로부터 위로 올라간다. 이 때, 만약 서로 같은 노드를 만나게되면 그게 최소공통조상이다. LCA 문제는 위 과정을 코드로 구현하면 풀 수 있으나 이 문제는 이방법으로는 풀 수 없다. 왜냐하면, 노드의 개수와 명령의 개수가 최대 10만개이므로 만약 리프노드에서 루트노드까지 찾는과정을 반복해야 한다면 시간초과가 날 수밖에없다...

[BOJ 2252(G2)리뷰] N명의 학생들을 키 순서대로 줄 세우려고한다. 이 때 학생들의 키를 알지 못하여 두 학생의 키를 비교한 결과를 통해 정렬하려고 한다. 예를들어, "1번학생이 3번보다 크고 3번학생이 2번보다 크다" 라고 한다면 이 세 학생의 키 순서는 1>3>2 가 될 것이다. 학생들의 정보가 주어졌을때 학생들의 키 순서대로 출력을 해야 한다. 이 문제는 위상정렬이라는 알고리즘을 통하여 해결할 수 있다. 주어진 정보를 그래프로 구성해보자. 만약 "1번학생이 3번보다 크다"라는 정보가 있다면 (1) > N >> M; for (int i = 0; i > a >> b; adj[a].push_back(b); indegree[b]++; } //inde..