[백준] 11403 - 경로 찾기 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 3 ~ 3 ++

 

---

링크

https://www.acmicpc.net/problem/11403 

11403번: 경로 찾기

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력
총 N개의 줄에 걸쳐서 문제의 정답을 인접 행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

접근방법

 모든 방향에 대해 경로를 탐색하고, 그 결과를 출력하는 문제이다. 모든 정점에 대해 경로를 구하는 문제이므로, 모든 정점에 대한 최단경로 알고리즘인 플로이드 알고리즘을 사용할 수 있다. 이것을 인지하고 풀이로 들어가자.

풀이

 풀 때, 플로이드 와샬 문제 같다고 생각이 들었다면, 이 문제 80%는 맞췄다. 기본적인 플로이드 와샬 문제와 다른 것은 해당 알고리즘은 모든 정점과 정점 사이의 최솟값을 구하는 알고리즘이고, 해당 문제는 경로의 존재 여부만을 묻고 있다.

따라서 해당 알고리즘을 조금 수정해야하는데, 알고리즘을 외워서만 푼다면, 아마 이 부분에서 발목이 잡힐 것 같다. 혹시라도 와샬을 쓰는 것까지 왔는데, 문제를 해결하지 못했다면, 플로이드 와샬에 대한 공부를 다시 하는 것이 좋을 것이다. 활용을 못하는 치명적인 문제이니...

 

앞서 계속말해왔듯, 우리는 경로가 있느냐 없느냐만 판단하면 된다. 따라서 존재하는 곳은 1 아닌 곳은 0으로만 표기하면 된다. 경로가 무한히 존재하는 곳도 INF로 놓을 필요 없이 그냥 존재한다는 의미로 1만 둬도 상관이 없다. 우리의 관심은 갈 수 있느냐 없느냐 뿐이다. 인접 노드를 거쳐 갈 때, 해당 종점 노드로 가기 위해선 다음과 같은 필수 조건이 있다.

 

• 시작점 i에서 k노드를 거쳐 j를 갈 때, i - k , k - j의 경로는 반드시 있어야 한다.

 최단 경로를 구하는 조건에서 위 조건으로 갈아 끼우기만 하면 문제는 깔끔하게 풀린다. 

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        Main test =new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk ;
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][N];

        for (int i = 0 ; i < N ;i++){
            stk = new StringTokenizer(br.readLine()," ");
            for (int j = 0 ; j < N ;j++){
                arr[i][j] = Integer.parseInt(stk.nextToken());
            }
        }

        solution(arr,N);

        StringBuilder sb = new StringBuilder();

        for (int[] row : arr){
            for (int atom : row){
                sb.append(atom+" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    private void solution (int[][] arr,int N){
	
    //floyd wharshall
        for (int k = 0 ; k < N ; k++){
            for (int i = 0 ; i < N ; i++){
                for (int j = 0; j < N ; j++){
                   if(arr[i][j]==0){
                   //i-k & k -j 모두가 경로가 존재한다면 
                        if(arr[i][k] !=0 && arr[k][j] !=0){
                            arr[i][j] = 1;
                        }
                   }
                }
            }
        }

    }


}

결과

 

 

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.