99클럽 코테 스터디 1일차 TIL (챌린저): [백준][C#] 11403 경로 찾기 - 실버1

 

문제 보기

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

 

 

풀이

문제를 풀러 갔더니 예전에 푼 문제다.

쓱 훑어봤는데 간단한 문제라 예전에 풀었던 풀이로 정리를 하기로 했다.

예제를 보며 풀이 방법을 생각해 보자.

우선 1열에서 갈 수 있는 모든 열을 구해 볼 건데, 우선 2열로 이동할 수 있어 보인다.

2열로 가면 3열로 이동할 수 있고, 3열로 가면 또 1열로 이동할 수 있다.

 

 

따라서 모든 열에서 모든 행으로 갈 수 있다는 소리다.

간단한 그래프 탐색 문제인데 한 번 그래프를 그림으로 그려 보면 이해가 더 빠를 것 같다.

 

모든 노드가 순환 연결이 되어 있다.

 

그럼 예제 2번도 그래프로 그려 보자.

자 이제 그래프로 그려 봤으니 남은 건 탐색이다.

나는 DFS를 사용 했다.

모든 열을 순회하며 해당 노드로의 경로가 확인 되면 반환 배열의 해당 인덱스를 1로 체크 했다.

for(int i = 0; i < N; i++)
{
    bool[] visited = new bool[N];
    for(int k = 0; k < N; k++)
    {
        if (metrix[i, k] == 1)
        {
            DFS(visited, i, k, N);
        }
    }
}

void DFS(bool[] visited, int id, int index, int N)
{
    if (!visited[index])
    {
        visited[index] = true;
        metrix[id, index] = 1;
        for (int i = 0; i < N; i++)
        {
            if (metrix[index, i] == 1)
            {
                DFS(visited, id, i, N);
            }
        }
    }
}

기본 적인 그래프 탐색이라 따로 설명할 건 없는 것 같다.

 

 

전체 코드

using System;
using System.Collections.Generic;

namespace BackjoonCodingTest
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            int N = int.Parse(reader.ReadLine());
            int[,] metrix = new int[N, N];
            for(int i = 0; i < N; i++)
            {
                string[] inputs = reader.ReadLine().Split();
                for(int j = 0; j < N; j++)
                {
                    metrix[i, j] = int.Parse(inputs[j]);
                }
            }

            for(int i = 0; i < N; i++)
            {
                bool[] visited = new bool[N];
                for(int k = 0; k < N; k++)
                {
                    if (metrix[i, k] == 1)
                    {
                        DFS(visited, i, k, N);
                    }
                }
            }

            for( int i = 0; i < N; i++)
            {
                for(int j = 0; j < N; j++)
                {
                    print.Write(metrix[i, j] + " ");
                }
                print.WriteLine();
            }

            void DFS(bool[] visited, int id, int index, int N)
            {
                if (!visited[index])
                {
                    visited[index] = true;
                    metrix[id, index] = 1;
                    for (int i = 0; i < N; i++)
                    {
                        if (metrix[index, i] == 1)
                        {
                            DFS(visited, id, i, N);
                        }
                    }
                }
            }
        }


    }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Silver/11403.%E2%80%85%EA%B2%BD%EB%A1%9C%E2%80%85%EC%B0%BE%EA%B8%B0

CodingTest_AutoSave/백준/Silver/11403. 경로 찾기 at main · MetroDefro/CodingTest_AutoSave