[백준] 11403 - 경로 찾기

1. 문제

11403번: 경로 찾기

2. 개요

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

3. 풀이 및 코드

3-1. 풀이

모든 정점에 대한 경로를 판단하기 위해 플로이드 워셜로 풀었다.

연결되어 있지 않은 정점은 충분히 큰 100000으로 초기값을 잡았다.

모든 정점에 대해 탐색이 끝났을 때, 값이 그대로 초기값인 경우 연결되지 않았다는 것이므로 이 때만 0으로 바꿔 출력해주면 된다.

3-2. Python

import sys

N = int(sys.stdin.readline())

graph = []

for i in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))

    for j in range(N):
        if graph[i][j] == 0:
            graph[i][j] = 100000

for mid in range(N):
    for s in range(N):
        for e in range(N):
            if graph[s][e] > graph[s][mid] + graph[mid][e]:
                graph[s][e] = graph[s][mid] + graph[mid][e]

for row in graph:
    for num in row:
        if num == 100000:
            print(0, end = ' ')
        else:
            print(1, end = ' ')

    print()

3-3. C#

namespace boj_11403
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            int[,] graph = new int[N, N];
            for (int i = 0; i < N; i++)
            {
                int[] rowinput = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                for (int j = 0; j < N; j++)
                {
                    if (rowinput[j] != 0)
                        graph[i, j] = rowinput[j];

                    else
                        graph[i, j] = 100000;
                }
            }

            for (int mid = 0; mid < N; mid++)
            {
                for (int s = 0; s < N; s++)
                {
                    for (int e = 0; e < N; e++)
                    {
                        if (graph[s, e] > graph[s, mid] + graph[mid, e])
                            graph[s, e] = graph[s, mid] + graph[mid, e];
                    }
                }
            }

            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    if (graph[i, j] != 100000)
                        Console.Write($"1 ");
                    else
                        Console.Write($"0 ");
                }
                Console.WriteLine();
            }
        }
    }
}