반응형 그래프2 [백준 20188] 등산 마니아 등산 마니아(20188)문제 출처 : https://www.acmicpc.net/problem/20188 이 문제는 2020년 정보올림피아드 2차 대회 초등부 3번, 중등부 2번 문제 입니다.문제 이해하기한 번만 읽어서는 잘 이해하기 힘든 문제 입니다. 특히나 다양성이라는 용어가 중요한데 이 말의 뜻이 어렵습니다.다양성은 길에 포함된 오솔길의 개수로 정의된다.이렇게 정의 되어 있습니다. 문제를 제대로 읽지 않으면 다양한 경로의 개수로 잘못 이해하기 쉽습니다. 문제를 잘 읽어보면 이 문제에서 원하는 다양성은 두 지점을 지나는 간선의 개수 입니다. 이 간선의 개수는 최단 경로를 뜻하는 것이 아니라 정상 즉 루트를 지나는 경로입니다.위와 같이 6, 7을 연결하는 다양성은 루트 부터 각 번호까지 간선의 개수 3.. 2024. 11. 22. [백준 1865] 웜홀 문제 출처 : https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 웜홀은 시간이 거꾸로 가는 곳입니다. 따라서 최단 경로를 구할 때 음의 가중치를 가진 간선이라 생각하면 됩니다. 이 문제에서는 음의 사이클이 존재하는지 존재하지 않는지 확인하는 문제입니다. 벨만 포드 알고리즘을 사용하여 음의 사이클이 있다면 YES를, 음의 사이클이 없다면 NO를 출력하는 문제입니다. 다빈치코딩 알고리즘에 벨만포드 알고리즘을 설명해 놓았습니다. 벨만포드 .. 2023. 8. 30. 이전 1 다음 반응형
