11403번 경로찾기 DFS 재귀

이 문제는 DFS 기초 문제이다. 하지만 재귀로 풀려고했을때 처음에는 시간 초과가 나서 약간 삽질을 좀 했다..

문제는 우선 1->2->3으로 갈수 있을때 1->3으로도 갈수있으므로  W[1][3]도 갈수있다고 1로 체크해주는 문제이다.

즉 중간에 몇개를 거쳐서라도 갈수 있으면 그 경로는 갈수있다고 체크를 해준다.

워셜-플로이드 알고리즘으로도 풀수 있지만 나는 dfs를 연습하고 싶어서 굳이 dfs로 풀었다.

첫번째 예제로 설명을 하자면,

1->2 , 2->3 , 3->1로 갈수있는 경로가 있다.

먼저 첫번째 정점인 1번 정점에서 갈수있는 경로를 모두 조사한다.

for(int i=1; i<=n; i++)

    {

        for(int j=1; j<=n; j++)

        {

           if(!visited[i][i] && input[i][j])

               go(i,i,j);

        }

    }

void go(int top,int x,int y)

{

    input[top][y] = 1;

    visited[top][y] = true;

    for(int i=1; i<=n; i++)

    {

        if(!visited[top][i] && input[y][i])

            go(top,y,i);

    }

    

}

top이란것은 몇번째 정점에서 시작한것이냐다. 즉 1번정점에서 갈수있는 모든 정점을 조사하고싶을때 top은 1이며 1번정점에서 갈수있는 경로를 모두 조사하기 전까지는 top은 바뀌지 않는다.

1번정점을 모두 조사하면

2번정점,

3번정점에서 갈수있는 모든 경로를 다 조사하게 되면 재귀를 멈추게 된다.

그리고 각 정점에서 시작했을때 그 정점을 방문했다는것을 표시를 해놔야 같은 계산을 피할수있기 때문에 visited라는 2차원 배열을 사용하였다. 이것을 사용하지 않으면 시간초과가 나기때문에 무조건 써줘야한다. 트리를 그리면서 생각해보면 이 코드를 쉽게 이해할수 있을것이다.

전체코드

#include <iostream>

using namespace std;

int input[101][101];

bool visited[101][101];

int n;

void go(int top,int x,int y)

{

    input[top][y] = 1;

    visited[top][y] = true;

    for(int i=1; i<=n; i++)

    {

        if(!visited[top][i] && input[y][i])

            go(top,y,i);

    }

    

}

int main()

{

    scanf("%d",&n);

    for(int i=1; i<=n; i++)

        for(int j=1; j<=n; j++)

            scanf("%d",&input[i][j]);

    

    for(int i=1; i<=n; i++)

    {

        for(int j=1; j<=n; j++)

        {

           if(!visited[i][i] && input[i][j])

               go(i,i,j);

        }

    }

    

    for(int i=1; i<=n; i++)

    {

        for(int j=1; j<=n; j++)

            printf("%d ",input[i][j]);

        printf("\n");

    }

    

    return 0;

}