99클럽 코테 스터디 1일차 - 백준 경로찾기

문제

풀이

문제 해석

1. 가중치가 없는 그래프가 주어진다.

2. 행렬로 주어지는데 i, j좌표는 i가 j로 가는 간선이 있다는 뜻이다.

3. i에서 출발해서 j까지 닿을 수 있다면 1로 아니면 0으로 표시한다

풀이 방법

1. 정점이 100개로 작다.

2. 플로이드 - 워셜 알고리즘을 적용한다.

코드

package online.judge.baekjoon;

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

/**
 * 경로 찾기
 * 실버 1
 * 문제해석
 * 0~n까지 값이 특정 인덱스에 닿을 수 있는지 알아보는 문제
 *
 * 문제 풀이
 * 플로이드-워셜을 사용해서 닿을 수 있다면 1로 그래프 1로 변경
 */
public class No11403 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] graph = new int[n][n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //플로이드 워셜
        for (int i = 0; i < n; i++) {   //중간
            for (int j = 0; j < n; j++) {   //시작
                for (int k = 0; k < n; k++) {   //끝
                    if(graph[j][i] == 1 && graph[i][k] == 1){
                        graph[j][k] = 1;
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(graph[i][j]).append(' ');
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
}

 

TIL

• 플로이드-워셜 알고리즘을 다시 생각해 냈다.
• 이미 3년 전에 풀어봤던 문제였는데 기억이 전혀 안 났고 그 당시에도 같은 알고리즘을 사용했는데 이거 또한 기억이 전혀 없다. 인터넷에서 그냥 검색해서 풀이해 봤던 나를 반성한다.