[C++] 백준 11403번: 경로 찾기

🔗 문제

11403번: 경로 찾기

11403번: 경로 찾기

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지

 

🖍 풀이

DFS를 이용하여 풀었다.

N개의 각 정점으로 부터 DFS를 이용해 연결된 모든 정점을 visited로 표시했다.

여기서 DFS에서 사이클을 무한반복하지 않도록 방문하지 않은 정점으로만 가는 조건을 반드시 걸어주어야 한다.

 

💾  소스

#include <iostream>

const int MAX  = 100 + 1;

bool graph[MAX][MAX];
bool visited[MAX] = {false, };
int N = 0;

void DFS(const int idx)
{
    for(int i=0; i<N; ++i)
    {
        if(graph[idx][i] && !visited[i]) // visited로 사이클 방지
        {
            visited[i] = true;
            DFS(i);
        }
    }
}

int main()
{
    std::cin >> N;

    for(int i=0; i<N; ++i)
        for(int j=0; j<N; ++j)
            std::cin >> graph[i][j];

    
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<N; ++j)
        {
        	// 연결된 간선을 타내려간다.
            if(!graph[i][j] || visited[j]) continue; // visited로 사이클 방지
   
            DFS(j);

            for(int k=0; k<N; ++k)
            {
                if(!visited[k]) continue;
                //i-j가 연결되어서 타고 갔는데 k도 방문 했다? 
                //i-k도 연결되있다. 인접행렬에 표시
                graph[i][k] = true;
                
                // 다음 시작 정점을 위해 초기화
                visited[k] = false;
            }
        }
    }

    //std::cout << "==============\\n";
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<N; ++j)
            std::cout << graph[i][j] << ' ';
        std::cout << '\\n';
    }

    return 0;
}