BFS19 [알고리즘] Directed Graph에서 사이클 찾기 방향이 있는 그래프에서 싸이클을 찾는 방법을 알아보자. Using BFS Kahn 알고리즘을 사용한다. www.geeksforgeeks.org/detect-cycle-in-a-directed-graph-using-bfs/ Detect Cycle in a Directed Graph using BFS - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.. 2023. 4. 15. [백준 5214] 환승 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 느낌상 bfs를 사용해야 하는 것을 알겠으나 연결 그래프를 만들 때 모든 노드 각각에 대해 연결선을 만들면 시간 초과가 발생하는 문제이다. 이 때 사용하는 방법은 바로 더미노드를 만드는 것이다. 더미 노드를 만들어서 허브로 사용하여 노드를 연결한다. 1~n까지는 진짜 노드이고 n+1부터 더미 노드를 설정한다. 더미 노드의 경우 거리가 0으로 처리되게끔 한다. /* 환승 .. 2021. 7. 5. [백준 1948] 임계경로 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 위상정렬 + 역추적 문제이다. 문제이해가 어려웠으나 요약하면 1. 시작점->목적지까지 도달하는데 가장 오래 걸리는 시간 구하기 2. 1만큼의 시간이 소요되는 경로에 속한 도로들의 수 구하기 이다. 1분도 쉬지 않는다는 의미가 2라는 걸 이해하지 못했다... 1을 푸는 것은 위상정렬 + dp를 결합하면 어렵지 않게 해결할 수 있으나 문제는 2였다. 2에 대해 set으로 풀.. 2021. 6. 19. [백준 15591] Moo Tube www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 문제대로 풀면 TLE 발생 처음 접근 방법: 플로이드 와샬 알고리즘처럼 모든 경로에서의 최단 거리를 구하려했다. TLE 발생 -> 개선: BFS 사용. 모든 경로에서의 최단 거리를 구할 필요가 없다. 조건이 있는 BFS 문제였다. 문제의 목적은 start노드에서 USADO가 K이상인 노드 수를 세는 게 목적이다. i->a의 USADO는 min(i->j, j->.. 2021. 2. 17. 이전 1 2 3 4 5 다음
