[Python][C++] 11403번 경로 찾기

문제

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

 

 

 

 

코드

1. Python

import sys

input = sys.stdin.readline  # 빠른 입력을 위해 sys.stdin.readline 사용

# 정점의 수 n 입력받기
n = int(input())

# 그래프의 인접 행렬 입력받기
graph = [list(map(int, input().split())) for _ in range(n)]

# 플로이드-워셜 알고리즘 적용
# 모든 정점 쌍 (i, j)에 대해 경로가 존재하는지 확인
for k in range(n):  # 경유할 정점 k
    for i in range(n):  # 출발 정점 i
        for j in range(n):  # 도착 정점 j
            # 정점 i에서 j로 가는 경로가 없는데, i에서 k를 거쳐 j로 가는 경로가 있다면
            if graph[i][k] and graph[k][j]:
                graph[i][j] = 1  # 경로가 있음을 표시

# 결과 출력
for g in graph:
    print(*g)  # 각 행을 공백으로 구분하여 출력

 

2. C++

#include <iostream>
#include <queue>
using namespace std;

int n;  // 그래프의 노드 수
int board[100][100];  // 인접 행렬을 저장할 배열

// 너비 우선 탐색(BFS) 함수
void bfs(int x) {
    queue<int> q;  // BFS 탐색을 위한 큐
    int visited[100] = {};  // 방문 여부를 체크할 배열

    q.push(x);  // 시작 노드를 큐에 추가

    while (!q.empty()) {
        int cx = q.front();  // 현재 노드
        q.pop();

        // 현재 노드와 연결된 모든 노드를 탐색
        for (int nx = 0; nx < n; nx++) {
            // 연결되어 있고 방문하지 않은 노드일 경우
            if (board[cx][nx] && !visited[nx]) {
                q.push(nx);  // 연결된 노드를 큐에 추가
                visited[nx] = 1;  // 방문 처리
                board[x][nx] = 1;  // 시작 노드에서 해당 노드까지 도달할 수 있음을 표시
            }
        }
    }
}

int main() {
    cin >> n;  // 노드의 수 입력

    // 인접 행렬 입력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }

    // 각 노드에 대해 BFS 수행
    for (int i = 0; i < n; i++) {
        bfs(i);
    }

    // 결과 출력: 각 노드에서 다른 노드까지 도달 가능한지 여부
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << board[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}

 

 

풀이 

1. 플로이드-워셜
   1. 플로이드-워셜 알고리즘 사용:
      • 플로이드-와샬 알고리즘은 그래프에서 모든 정점 쌍 사이의 최단 경로를 찾는 알고리즘
      • 가중치가 없는 단순 경로 존재 여부만 확인하면 되기 때문에, 플로이드-와샬 알고리즘을 사용하여 경로의 존재 여부를 계산
      • graph[i][j]를 초기 상태로 두고, 플로이드-와샬 알고리즘을 통해 모든 i, j에 대해 경로가 존재하는지 갱신
   2. 경로 갱신:
      • 플로이드-와샬을 통해 중간에 정점 k를 거쳐 가는 경로가 존재하면 graph[i][j]를 1로 업데이트. 즉, graph[i][k]가 1이고 graph[k][j]가 1이면 graph[i][j]를 1로 설정
      • 이 과정을 모든 정점 쌍에 대해 반복
   3. 결과 출력:
      • 모든 정점 쌍 사이의 경로 존재 여부를 최종적으로 출력
2. BFS
3. 1. BFS를 통한 경로 탐색:
      • 각 정점 i에 대해 BFS를 수행하여 정점 i에서 도달할 수 있는 모든 정점을 탐색
      • BFS를 통해 탐색한 도달 가능한 정점을 찾을 때마다, graph[i][j] 값을 1로 업데이트하여 i에서 j로의 경로가 존재함을 표시
   2. 결과 갱신:
      • BFS 탐색 중에 도달 가능한 모든 노드들을 찾고, 이를 graph에 바로 업데이트
   3. 결과 출력:
      • 모든 정점 쌍 사이의 경로 존재 여부를 최종적으로 출력