백준 11403번: 경로 찾기 (C++)

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

모든 점을 방문할 수 있는지 확인하면 되는 문제이므로 bfs / dfs로 기본적으로 접근할 수 있다.

또한 n이 작기 때문에 플로이드 와샬도 가능하다. 가중치는 모두 1로 두면 되겠다.

이러한 문제를 풀 때 신경써줄 부분은, 자기 자신을 곧바로 방문할 수 있는지 확인하는 것이다.

이 문제에서는 노드1->노드1 이런식으로 곧바로 자기 자신을 방문할 수 없고, 1->2->3->1 이런식으로 사이클을 거쳐서 root(자기 자신)을 방문할 수 있다.

따라서 플로이드 와샬 알고리즘을 적용할 때, 비용을 무한대로 초기화 하는 과정에서, 자기 자신으로 가는 비용도 무한대로 초기화해주고 시작해야 한다.

비슷한 맥락으로, DFS로 문제를 풀이할 때, 보통 시작점을 방문처리하고 알고리즘을 시작한다.

하지만 시작점을 방문처리하고, 미방문한 지점을 이어서 방문하도록 알고리즘을 구현하면

1-> 2-> 3-> 1  이 과정에서, 마지막에 3->1을 방문할 수가 없다. 초기에 시작 지점인 1을 방문처리 했기 때문이다.

따라서 이것을 방지하기 위해서 시작지점을 방문처리하지 않는다. 3->1을 거쳐서 시작 지점에서 다시 for 문을 돌면 어짜피 갈 수 있는 곳이 없으므로 재귀를 탈출하게 된다.

1. DFS

#pragma warning(disable :4996)
#include<iostream>
using namespace std;
 
int m[101][101];
bool vis[101][101], chk[11];
int n, root;
void dfs(int cur) {
 
    for (int i = 0; i < n; i++) {
        if (m[cur][i] == 1 && !chk[i]) {
            chk[i] = true;
            dfs(i);
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> m[i][j];
    //cout << '\n';
 
    for (int i = 0; i < n; i++) {
        dfs(i); // i->i로 곧바로 갈 수 없으므로 시작점 방문처리 안 함
 
        //노드i에서 시작해서 방문할 수 있는 점들 표시
        for (int j = 0; j < n; j++) {
            if (chk[j]) cout << 1 << ' ';
            else cout << 0 << ' ';
        }
        cout << '\n';
 
        //초기화
        for (int i = 0; i < n; i++) 
            chk[i] = false;
        
    }
 
    return 0;
}
 

2. 플로이드 와샬

#include<iostream>
#include<algorithm>
#define INF 100000
using namespace std;
 
int n; //정점 개수
int m[101][101];
 
void FW() { //플로이드 와샬
    for (int k = 0; k < n; k++)
        for (int j = 0; j < n; j++)
            for (int i = 0; i < n; i++)
                m[i][j] = min(m[i][j], m[i][k] + m[k][j]);
}
int main(void) {
 
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
        
            cin >> m[i][j];
            if (m[i][j] == 0 ) m[i][j] = INF;
            //자기 자신으로 갈 수 없다고 봄 -> 자기 자신으로 가는 비용도 무한초기화
        }
    
    FW();
 
    //cout << '\n';
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (m[i][j] == INF) //비용이 무한 -> 방문할 수 없다는 의미
                cout << 0 << ' ';
            else
                cout << 1 << ' ';
        }
        cout << '\n';
    }
    
    
    return 0;
}