BAEKJOON / 백준 - JAVA 11403번 경로 찾기

2024.07.27기준 - 실버1

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 주어진 정점과 인접 행렬이 주어졌을 때, 인접 행렬을 통해 갈 수 있는 곳을 1로 못가는 곳을 0으로 해서 출력하는 문제입니다.

 

이 문제에 접근하기 위해서 플로이드 위셜 알고리즘을 통해 접근을 하였습니다.

 

플로이드 워셜 알고리즘
그래프 내 모든 정점 쌍의 최단 경로를 반복적으로 계산합니다.
두 정점 사이의 최단 경로가 어떤 중간 정점을 거쳐서 갈 때 더 잛은지를 확인하여 입력하는 방식입니다.

플로이드 위셜 알고리즘 작동 과정
1. 초기화
● 그래프의 인접 행렬 d를 사용합니다. 여기서 d[i][j]는 정점 i에서 정점 j로 가는 초기 가중치를 의미합니다.
● 만약 i에서 j로 직접적인 간선이 없다면 d[i][j]를 무한대로 설정합니다. 그러나 자기 자신으로의 경로는 0으로 설정합니다. (d[i][i] = 0)

2. 경로 업데이트
● 중간 점걸 k를 차례로 고려하면서, 경로 i → j를 업데이트 합니다.
● 새로운 경로의 비용은 d[i][j]와 d[i][k] + d[k][j] 중 더 작은 값으로 결정합니다.

 

1. 입력받은 정점과 인접 행렬로 최단 거리 테이블을 생성합니다.

1-1. 2차원 배열을 생성해 테이블의 정보를 입력해줍니다.
1-2. 무한을 가정한 값을 1000000이라고 가정을 하고 입력을 했습니다.

int[][] node = new int[n][n];
int max = 1000000; // 무한

int l;
StringTokenizer st;
for (int i = 0; i < n; i++) {
    st = new StringTokenizer(br.readLine());

    for (int j = 0; j < n; j++) {
        l = Integer.parseInt(st.nextToken());

        if (l == 1) {
            node[i][j] = 1;
        } else {
            node[i][j] = max;
        }
    }
}

 

2. 플로이드 워셜 알고리즘을 이용해 최단 거리를 테이블에 입력해줍니다.

for (int k = 0; k < n; k++) { // 거쳐가는 정점
    for (int i = 0; i < n; i++) { // 출발 정점
        for (int j = 0; j < n; j++) { // 도착 정점
            node[i][j] = Math.min(node[i][j], node[i][k] + node[k][j]);
        }
    }
}

 

2-1. 중간 정점이 0일 때, 테이블의 변화 (i = 0)

d[2][1] = min(d[2][1], d[2][0] + d[0][1]) = min(1000000, 2) = 2

중간 정점이 0일 때, 최단 거리가 하나 업데이트 되었습니다.

 

2-2. 중간 정점이 1일 때, 테이블의 변화 (i = 1)

d[0][2] = min(d[0][2], d[0][1] + d[1][2]) = min(1000000, 2) = 2

d[2][2] = min(d[2][2], d[2][1] + d[1][2]) = min(1000000, 3) = 3

중간 정점이 1일 때, 총 2가지 최단 거리가 업데이트 되었습니다.

 

2-3. 중간 정점이 2일 때, 테이블의 변화 (i = 2)

d[0][0] = min(d[0][0], d[0][2] + d[2][0]) = min(1000000, 3)  = 3

d[1][0] = min(d[1][0], d[1][2] + d[2][0]) = min(1000000, 2) = 2

d[1][1] = min(d[1][1], d[1][2] + d[2][1]) = min(1000000, 3) = 3

중간 정점이 2일 때, 총 3가지의 최단 거리가 업데이트 되었습니다.

 

3. 최단 거리가 무한이 아닌 곳은 갈 수 있는 곳 이기 때문에, 1로 출력 무한이라면 0으로 출력을 해줍니다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (node[i][j] >= max) { // 갈 수 없다면 0
            sb.append(0).append(" ");
        } else { // 갈 수 있다면 1
            sb.append(1).append(" ");
        }
    }
    sb.append("\n");
}

 

 

코드

package Main;

import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine()); // 정점의 개수
		
		int[][] node = new int[n][n];
		int max = 1000000; // 무한
		
		int l;
		StringTokenizer st;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < n; j++) {
				l = Integer.parseInt(st.nextToken());
				
				if (l == 1) {
					node[i][j] = 1;
				} else {
					node[i][j] = max;
				}
			}
		}
		
		for (int k = 0; k < n; k++) { // 거쳐가는 정점
			for (int i = 0; i < n; i++) { // 출발 정점
				for (int j = 0; j < n; j++) { // 도착 정점
					node[i][j] = Math.min(node[i][j], node[i][k] + node[k][j]);
				}
			}
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (node[i][j] >= max) { // 갈 수 없다면 0
					sb.append(0).append(" ");
				} else { // 갈 수 있다면 1
					sb.append(1).append(" ");
				}
			}
			sb.append("\n");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
}