백준 11403 경로 찾기

작성일 | In |

Problem : 경로 찾기

유형 : 플로이드 워셜, DFS

문제 해석

  • 점에서 다른 점으로 가는 경로가 있는지를 확인하라.

문제 재해석

  • 모든 점에서 다른 점들까리의 관계를 확인한다.

해결 전략

  • Floyd 를 통해 각 점들 간의 관계를 전부 확인한다.
  • DFS 를 통해 그래프를 순회하여 확인한다.

설계, 구현

Floyd

  • 갈 수 있는지 확인한다.
  • 갈 수 없다면 다른 경로를 거쳐서 갈 수 있는지 확인한다.
  • 다른 경로를 거쳐서 갈 수 있다면, 갈 수 있다고 표시한다.

DFS

  • 한 점에서 부터, 연결된 모든 그래프릃 확인한다.
  • 연결된 그래프에서 또 연결된 곳을 전부 방문해본다.

주의사항

  • DFS 구현시 시작점은 처음 시작점으로 고정 해야한다.
  • 왜냐 햐면, 한 점에서의 모든 관계를 찾아가는 과정이기 때문이다.

디버깅

  • DFS 할때 인자를 잘못 주었었다.
    • 연결된 노드를 첫번째 인자로 주었었다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
using namespace std;

int n;
int node[102][102], visited[102][102];

void Print_Answer() {
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n; ++ii) {
            cout << visited[i][ii] << " ";
        }
        cout << "\n";
    }
}

#if 0
void Floyd() {
    for (int visit = 0; visit < n; ++visit) {
        for (int st = 0; st < n; st++) {
            for (int ed = 0; ed < n; ++ed) {
                if (node[st][ed]) visited[st][ed] = 1;
                else {
                    if (visited[st][visit] && visited[visit][ed]) {
                        visited[st][ed] = 1;
                    }
                }
            }
        }
    }
}

void Solve() {
    Floyd();
    Print_Answer();
}

#else


void Dfs(int start_node, int connect_node) {

    for (int nxt_node = 0; nxt_node < n; ++nxt_node) {
        if (node[connect_node][nxt_node] && !visited[start_node][nxt_node]) {
            visited[start_node][nxt_node] = true;
            Dfs(start_node, nxt_node);
        }
    }
}
#endif

void Solve() {
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n; ++ii) {
            if (node[i][ii] && !visited[i][ii]) {
                visited[i][ii] = true;
                Dfs(i, ii);
            }
        }
    }
    Print_Answer();
}



void Input() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n; ++ii) {
            cin >> node[i][ii];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • 그래프 순회 문제를 갑자기 헷갈려 했다.
  • 경험치의 문제다. 더 연습하자.