코딩 테스트 [그래프] - 경로 찾기

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

(시간 제한 1초)

---

입력

1번째 줄에 노드의 개수 N(1 ≤ N ≤ 100), 2번째 줄부터 N개의 줄에 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1일 경우에는 i에서 j로 가는 에지가 존재한다는 뜻이고, 0일 경우에는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

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

예제 입력
3
0 1 0
0 0 1
1 0 0
 
예제 출력
1 1 1
1 1 1
1 1 1

---

1단계 - 문제 분석하기

플로이드-워셜 알고리즘을 이용해 풀 수 있는 문제다. 단, 최단 거리를 구하는 문제가 아니기에 최단 거리를 업데이트 하는 부분만 조금 수정한다.

2단계 - 손으로 풀어 보기

1 입력 데이터를 행렬에 저장한다.

2 수정한 플로이드-워셜 알고리즘을 수행한다. S와 E가 모든 중간 경로(K) 중 1개라도 연결돼 있다면 S와 E는 연결 노드로 저장한다.

3 알고리즘으로 변경된 인접 행렬을 출력한다.

3단계 - sudo코드 작성하기

N(인접 행렬의 크기)
distance(노선 데이터를 저장하는 인접 행렬)

for(i -> N만큼 반복)
{
	for(j -> N만큼 반복)
    {
    	인접 행렬 데이터를 distance 행렬에 저장
    }
}

for(k -> N만큼 반복)
{
	for(i -> N만큼 반복)
    {
    	for(j -> N만큼 반복)
        {
        	i ~ j사이의 모든 경로를 탐색
            만약 distnace[i][k] == 1 && distnace[k][j] == 1 이라면
            	distance[i][j] = 1
        }
    }
}

distance 배열 출력

4단계 - 코드 구현하기

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

public class Q62 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[][] distance = new int[N+1][N+1];

        for(int i = 1; i < N + 1; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j < N + 1; j++){
                distance[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int k = 1; k < N + 1; k++){
            for(int i = 1; i < N + 1; i++){
                for(int j = 1; j < N + 1; j++){
                    if(distance[i][k] == 1 && distance[k][j] == 1)
                        distance[i][j] = 1;
                }
            }
        }

        for(int i = 1; i < N + 1; i++){
            for(int j = 1; j < N + 1; j++){
                System.out.print(distance[i][j] + " ");
            }
            System.out.println();
        }

        br.close();
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편