'알고리즘/BOJ' 카테고리의 글 목록 (3 Page)

[BOJ] 11657 타임머신

2023.09.08

✨ 최단경로 알고리즘 ➡️ 벨만 포드 알고리즘 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 📍 고려해야할 점 C < 0 인 경우 타임머신으로 시간을 되돌아가는 경우이다. ➔ 음의 가중치 존재 1번 도시에서 출발한다. 음의 사이클이 있거나 경로가 아예 없다면 -1 출력 오버플로우 범위 조심 🕹️ 풀이과정 1️⃣ 간선과 정점, 비용의 정보를 저장한다. 2️⃣ 벨만 포드 알고리즘을 사용..

알고리즘/BOJ

[BOJ] 1865 웜홀

2023.09.08

✨ 최단경로 알고리즘 ➡️ 벨만 포드 알고리즘 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 📍 고려해야할 점 한 지점에서 출발하여 다시 출발했던 지점으로 돌아왔을 때 처음 출발했을 때보다 시간이 되돌아가 있는 경우 판단 ➔ 웜홀 내에서 시간이 거꾸로 흘러간다. ➡️ 음수 가중치 존재 & 음의 사이클 존재 O 한 지점에서 출발한다. (특정 지점에서 출발 X) 임의의 정점에서 출발 모든 정점에서 출발 두 지점을 연결하는 도로가 한 ..

알고리즘/BOJ

[BOJ] 1939 중량제한

2023.09.07

✨ Binary Search + BFS/DFS https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 📍 고려해야할 점 두 섬 사이에 여러 개의 다리가 있고 양방향이다. 공장이 있는 두 섬을 연결하는 경로가 반드시 존재한다. (반드시 존재하는 경로의 입력값만 주어짐) 옮길 수 있는 물품의 최대 중량 구하기 🕹️ 풀이과정 1️⃣ 입력값으로 주어진 다리 정보 저장 (a섬과 b섬 사이에 중량제한이 ..

[BOJ] 11657 타임머신

[BOJ] 1865 웜홀

[BOJ] 1939 중량제한

티스토리툴바