[BOJ/Java] 11562. 백양로 브레이크

[BOJ/Java] 11562. 백양로 브레이크

11562번: 백양로 브레이크

---

문제 해석

이 문제는 학교의 건물 간 통행로를 양방향으로 통행할 수 있게 만드는 데 필요한 최소 비용을 계산하는 문제이다. 각 통행로는 일방통행 또는 양방향 통행이 가능하며, 일방통행로를 양방향으로 바꾸는 데에는 비용이 든다.

풀이 과정

제출된 코드는 플로이드-와샬 알고리즘을 사용하여 모든 쌍 최단 경로를 계산한다. 각 건물 간의 최소 비용을 담은 그래프에서, 일방통행로의 경우 양방향으로 변경할 때 추가 비용을 고려한다. 이후 주어진 쿼리에 대해 각 건물 쌍의 최소 변경 비용을 출력한다.

코드

package edu.ssafy.im.BOJ.Gold.G3.No11562;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		new Main().sol();
	}

	private int N; // 건물의 개수
	private int M; // 통행로의 개수
	private int[][] graph; // 각 건물 간의 최소 비용 그래프
	private int K; // 쿼리의 수

	private void sol() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		// 초기화: 본인정점으로 가는 비용은 0, 그 외는 매우 큰 값으로 설정
		graph = new int[N][N];
		for (int i = 0; i < N; i++) {
			Arrays.fill(graph[i], 100_000);
			graph[i][i] = 0;
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1; // 0-based index
			int v = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken());
			graph[u][v] = 0; // 일방통행 가능
			if (b == 1) graph[v][u] = 0; // 양방향
			else graph[v][u] = 1; // 일방통행을 양방향으로 변경할 경우 비용 1
		}

		FloydWarshall(); // 플로이드-와샬 알고리즘 수행

		K = Integer.parseInt(br.readLine());
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1;
			int v = Integer.parseInt(st.nextToken()) - 1;
			sb.append(graph[u][v]).append("\n");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private void FloydWarshall() {
		// 모든 쌍 최단 경로 계산
		for (int k = 0; k < N; k++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
				}
			}
		}
	}
}

시간 복잡도 분석

이 코드는 플로이드-와샬 알고리즘을 사용하여 모든 건물 쌍 간의 최소 비용을 계산한다. 알고리즘의 시간 복잡도는 𝑂(𝑁^3)이며, 건물의 수 𝑁에 따라 연산량이 결정된다. 주어진 문제의 범위 내에서 이 알고리즘은 충분히 효율적으로 동작한다.

느낀점

플로이드-와샬 알고리즘을 사용하여 모든 건물 쌍 간의 최소 비용을 계산하는 과정을 통해, 그래프 알고리즘의 이해도를 높일 수 있었다. 복잡한 문제에서 적절한 알고리즘을 선택하고 구현하는 능력이 중요함을 다시 한번 깨달았다.