Algorithm/Graph Search Algorithm30 BOJ G2 2931 가스관 JAVA 2931번: 가스관 www.acmicpc.net 문제 읽기 쓸데없이 시간을 너무 많이 쓴 문제이다.. 좀 허탈한데.. 처음에는 M에서부터 Z까지 이어진 파이프로 이동하면서 더 이상 이동하지 못하는 부분이 있으면 해킹 당한 것으로 생각하고 해당 지점의 상하좌우를 보며 문제를 풀었다. 예제도 다 나왔는데 21%에서 계속 틀려서 질문 게시판도 다 뒤져봤지만, 글도 별로 없을 뿐더러 있는 반례도 다 맞다고 나왔다. 진짜 다른 어딘가에서 틀린 거 같았는데 도저히 찾지를 못했다!! 그래서 그냥 그렇게 탐색해서 지점을 찾지 말고, 모든 빈 칸을 돌면서 상하좌우를 보고 파이프를 연결해야 할 지 판단하는 방식으로 바꾸었다. 맵의 크기도 25x25면 매우 작기 때문에 완탐으로도 충분했다. 그냥 완탐으로 푸는 게 정신 건강.. 2024. 2. 16. BOJ G3 1865 웜홀 JAVA 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 문제 읽기 N개의 지점, M개의 도로와 W개의 웜홀(각각 양방향, 단방향)이 연결된 그래프가 주어진다. 도로는 시간 비용이 양수이고, 웜홀은 시간 비용이 음수라고 했으므로, 도로를 양의 가중치, 웜홀을 음의 가중치로 보면 되므로 밸만 포드를 사용하여 해결할 수 있다. 다만 문제에서 구하는 것은 최단 거리 그 자체가 아니라, 출발 지점에서 여행을 하고 돌아왔을 때, 시간이 출발 시점보다 더 전으로 가 있을 수 있는지 궁금한 것이다. 이 경우는 음의 가.. 2024. 2. 10. Bellman-Ford 알고리즘 흔히 그래프에서 최단 거리를 구하는 알고리즘은 다익스트라를 떠올리기 쉽다. 하지만 다익스트라는 음수 가중치가 있는 경우에는 사용이 불가능하다. 다익스트라에 대한 자세한 설명과 과정들은 다음 링크에서 볼 수 있다. 다익스트라, Dijkstra Algorithm 코딩 문제에서 많이 볼 수 있는 그래프와 관련된 알고리즘을 공부해보자. 그래프에서 최단 거리를 구하는 알고리즘은 다음과 같은 것들이 있다. 💡 그래프의 최단 거리 구하는 알고리즘 1. 다익 rue-mi.tistory.com 그럼 음수 가중치가 있는 그래프에 다익스트라를 적용하면 어떻게 되는지 한 번 해보자. 음수 가중치에 다익스트라? 다음 예시를 보자. 위 그래프에 다익스트라를 적용해보자. 시작점을 1로 하여 다른 모든 노드로의 최단 거리를 다익스트.. 2024. 2. 9. BOJ G2 9370 미확인도착지 JAVA 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제 읽기 일단 처음에 읽었을 때는 다익스트라로 풀면 되겠다 생각이 들었고, 그 사이에 g와 h 사이의 도로를 지나갔다면 별도의 배열로 표시해주자고 생각했다. 하지만! 예제는 나왔지만 제출했더니 틀렸다(근데 예제가 너무 유하게 줘서 웬만하면 예제는 다 맞고 내면 틀리는 거 같다. 그래서 정답 비율이 25%..) 그래서 질문 게시판 뒤져보니 이런 말들이 있었다. 글 읽기 - 반례를..모르겠습니다 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.ne.. 2024. 2. 8. 이전 1 2 3 4 5 6 7 8 다음
