Dijkstra3 [백준] 1504번: 특정한 최단 경로 (Java) 1. 문제설명방향성 없는 그래프에서 1번 정점에서부터 N번 정점으로 최단 거리로 이동하려 한다. 한 번 이동했던 정점 또는 간선을 다시 이동할 수 있다. 주어진 두 정점을 반드시 거치면서 최단 경로를 구하는 문제이다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식`Node` 객체를 사용하여 정점과 거리 정보를 저장한다.인접리스트 형식(`List[] list`)으로 간선 정보를 저장한다. (양방향으로)다익스트라 알고리즘을 사용한다.우선순위 큐를 사용하여 가장 짧은 경로를 먼저 처리하고, 현재 경로에서 더 짧은 경로를 찾으면 경로 정보를 갱신하는 방식으로 구현한다.두 가지 경로를 구한다.1 → v1 → v2 → N1 → v2 → v1 → N총 3번의 다익스트라 메서드 호출을 통해 두 가지 경로의 최.. 2024. 9. 10. [백준] 1238번: 파티 (Java) 1. 문제설명N개의 마을에 각각 한 명의 학생이 있다. 이 마을 사이에는 M개의 단방향 도로들이 있고 i번째 길을 지나는데 T(i)의 시간을 소비한다. 각각의 학생들을 최단 시간에 파티(X)에 오고 가기를 원한다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생을 구하는 문제이다.모든 학생은 집에서 X에 갈 수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식인접리스트 형식으로 그래프 정보를 입력받는다.정방향 그래프: X 마을에서 각 마을로 가는 경로를 구할 때 사용역방향 그래프: 각 마을에서 X 마을로 가는 경로를 구할 때 사용다익스트라 알고리즘을 두 번 실행한다.첫 번째: 정방향 그래프를 사용하여 X에서 각 마을로 .. 2024. 9. 10. [백준] 17396번: 백도어 (Java) 1. 문제설명0번째에서 N-1번째 분기점까지 가는 최단 거리를 구하는 문제이다. 이때 적의 시야에 걸리는 곳은 지나칠 수 없다. 시야 정보가 0이면 상대 시야에 보이지 않고, 1이면 상대 시야에 보인다. 시야에 걸리지 않으면서 N-1번째 분기점에 도달하는 최단 거리를 구한다.시간 제한: 2초메모리 제한: 512MB 2. 접근 방식`Node` 객체를 사용하여 각 노드(`end`)에 그 노드의 비용(`time`)을 저장하고, 우선순위 큐에서 경로 비용이 짧은 순서대로 처리된다.각 분기점 사이의 정보를 `List[] list` 에 저장한다. (인접리스트 방식, 양방향으로 저장)다익스트라 알고리즘을 사용하여 최단 거리를 구한다.우선순위 큐를 사용하여 가장 짧은 경로를 먼저 처리하고, 현재 경로에서 더 짧은 경로.. 2024. 9. 10. 이전 1 다음 반응형
