[Java] 백준 11403번 [경로 찾기] 자바

: ) YOUNG·2022년 3월 27일
3

알고리즘

목록 보기
70/417
post-thumbnail

백준 11403번
https://www.acmicpc.net/problem/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으로 출력해야 한다.


생각하기

Floyd-Warshall 맛보기

경로를 찾는 Floyd-Warshall 알고리즘의 기초 문제이다.

원래 플로이드 워셜 알고리즘의 최단 경로의 길이(가중치의 합)을 찾는 것이 목적인데,

이 문제는 단순히 방향 그래프에서 각 노드간에 이동할 수 있는지 없는지를 파악하는 문제였다.

진짜 기초를 다지기 위한 문제 너무 좋았음.

풀다 보니 느낀점은
동적 계획법도 들어가있고, 사실 부르트포스 개념도 들어가 있는 것 같다

그래프 전체를 완전탐색해서 노드간에 이동이 가능한지를 파악하는 것,

또한, 한번 노드간 이동이 가능하다는 것을 파악한 이후 부터는 1로 기록을 해서 다른 노드로 이동 가능하다는 것을 알 수 있다는 점

동작

우리가 일상 생활을 할때, 강을 건넌다고 생각해보자.
A -> B로 이동할 때, 다리를 건넌다고 한다면, 다리가 여기서 k의 개념이라고 생각하면 쉬울 것 같다

결국 어떤 곳으로 이동할 때, 하나씩 파악해서 다리가 하나라도 있으면 하나씩 하나씩 다리를 건너서(경로가 멀 지라도) 이동할 수 있는지 여부를 파악한다고 생각하면 쉽다

Find_Road() 함수가 경로를 찾게 해주는 함수이다.

for(int k=0; k<N; k++) {
			// i = 출발 노드			
			for(int i=0; i<N; i++) {
				// j = 도착 노드
				for(int j=0; j<N; j++) {
					// (i,k) -> (k, j) -> (k,i) 방향 그래프에서 다른 간선과 노드를 통해
					// 해당 노드로 이동이 가능한 가 를 판별

					if(arr[i][k] == 1 && arr[k][j] == 1) {
						arr[i][j] = 1;
					}
				}
			}
			
		}

해당 부분에서 k를 통해서 하나씩 이동 할 수 있는지 노드 사이에 연결되는 곳이 있는지를 파악하고
우리가 만들어놓은 arr행렬에서 갈 수 있다를 1로 기록해 놓으면
하나씩 arr에 1이 생기면서 전체를 탐색해서 갈 수 있는 노드간에
간선을 행렬로 표시해서 완성시키는 개념이다.

각 지역마다 갈 수 있냐 없냐를 지도로 만든다고 생각해보자.
어렵지 않게 이해할 수 있을 것이라고 믿는다!




코드


import java.io.*;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N;
    private static int[][] arr;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();
        
        floyd();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(arr[i][j]).append(' ');
            }
            sb.append('\n');
        }

        return sb.toString();
    } // End of solve()

    private static void floyd() {

        for (int i = 0; i < N; i++) { // 9번씩 0 9번
            for (int j = 0; j < N; j++) { // 3번씩 0 3번
                for (int k = 0; k < N; k++) { // 1번씩 0 1번
                    // (i, k) -> (k, j) -> (k, i)
                    if (arr[j][i] == 1 && arr[i][k] == 1) {
                        arr[j][k] = 1;
                    }
                }
            }
        }
    } // End of floyd()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());

        arr = new int[N][N];
        for (int i = 0; i < N; i++) {
            String temp = br.readLine();

            for (int j = 0; j < N; j++) {
                arr[i][j] = temp.charAt(j << 1) - '0';
            }
        }
    } // End of input()
} // End of Main class


>```

  
  

0개의 댓글