백준 11403번 [경로 찾기](C++) -yes6686- 티스토리

백준 문제 풀이: 11403 [경로 찾기]

---

문제 링크: https://www.acmicpc.net/problem/11403

문제 설명:

주어진 방향 그래프에서 두 정점 간에 경로가 존재하는지를 찾는 문제입니다. 그래프의 인접 행렬이 주어질 때, 정점 간의 경로가 존재하면 1, 존재하지 않으면 0을 출력합니다.

입력:

• 첫째 줄에 정점의 개수 n이 주어집니다. (1 ≤ n ≤ 100)
• 다음 n개의 줄에는 그래프의 인접 행렬이 주어집니다.

출력:

• 각 정점에서 다른 정점까지의 경로가 존재하면 1, 그렇지 않으면 0으로 이루어진 n x n 행렬을 출력합니다.

예시:

입력:
3
0 1 0
0 0 1
1 0 0

출력:
1 1 1
1 1 1
1 1 1

---

문제 해결 코드

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

int arr[101][101]; // 입력된 그래프의 인접 행렬
vector<int> adj[101]; // 각 정점의 인접 리스트
int visited[101]; // 방문 여부를 저장하는 배열

// 깊이 우선 탐색 (DFS) 함수
void dfs(int node) {
    for (int i = 0; i < adj[node].size(); i++) {
        int next = adj[node][i];
        if (visited[next] == 0) { // 방문하지 않은 노드만 탐색
            visited[next] = 1;
            dfs(next);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n; // 정점 개수 입력

    // 그래프 입력 및 인접 리스트 생성
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) adj[i].push_back(j);
        }
    }

    // 각 정점에 대해 DFS 수행
    for (int i = 1; i <= n; i++) {
        dfs(i); // i 정점에서 도달 가능한 정점을 탐색
        for (int j = 1; j <= n; j++) {
            cout << (visited[j] ? 1 : 0) << ' '; // 도달 가능 여부 출력
        }
        memset(visited, 0, sizeof(visited)); // 방문 배열 초기화
        cout << '\n';
    }

    return 0;
}

---

코드 설명

이 코드는 DFS를 활용하여 주어진 그래프에서 각 정점에서 다른 정점까지의 경로 존재 여부를 탐색합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘: 깊이 우선 탐색(DFS)을 사용하여 각 정점에서 도달 가능한 정점을 탐색합니다.
• 구현 세부사항:
  • adj[node]: 인접 리스트로 변환하여 그래프를 저장합니다.
  • visited[next]: 방문 여부를 기록하여 이미 탐색한 노드는 중복으로 탐색하지 않도록 합니다.
  • memset: 방문 배열 초기화를 통해 각 정점마다 독립적으로 탐색 결과를 확인합니다.
• 시간 복잡도 분석:
  • DFS 수행: O(n + m) (n은 정점의 개수, m은 간선의 개수)
  • 전체 탐색: O(n * (n + m))

---

결과

코드는 주어진 입력에 따라 각 정점 간의 경로 존재 여부를 확인하고, 이를 출력합니다. DFS를 활용하여 효율적으로 문제를 해결하며, 입력 크기에 따라 적절한 성능을 제공합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!