[BOJ] 11403 경로 찾기

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

11403번: 경로 찾기

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

플로이드-워셜 알고리즘

 

---------------------------------------------------풀이----------------------------------------------------

 

단순하게 플로이드-워셜 알고리즘을 적용하면 풀리는 문제라고 하는데, 조금 다르게 풀었다.

크게 3중 루프를 도는 개념은 똑같다.

for(i)

   for(j)

      for(k)

우선, i에서 j로 갈 수 있는지 체크한다.

map[i][j] 가 1이어서 i에서 j로 갈 수 있다면,

j에서 갈 수 있는 k들(map[j][k]==1)에 대해

i에서 k로 갈 수 있는 것도 true이다. 따라서, map[i][k]를 1로 업데이트 한다.

 

이 과정을 한 번 반복하면, 적용되지 않은 부분이 남아있기 때문에

다시 적용된 값들에 새로 바뀐 값들을 적용하기 위해

총 두 번 반복한다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

int map[101][101] = {0, };
int N;

void print_map(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
}

int main(void){
    FASTIO;
    cin >> N;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> map[i][j];
        }
    }

    // 이 과정을 총 두 번 반복
    for(int l = 0; l < 2; l++){
        // i에서 j로 갈 수 있다면, j에서 k로 가는 모든 가능한 곳을 i에서 k로 갈 수 있다고 표기
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                // i에서 j로 갈 수 있다면,
                if(map[i][j]){
                    for(int k = 0; k < N; k++){
                        // j에서 k로 갈 수 있는 모든 곳은 i에서 k로 갈 수 있음
                        if(map[j][k]){
                            map[i][k] = 1;
                        }
                    }
                }
            }
        }
    }

    print_map();
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

union&find를 떠올렸지만, directed graph이므로 단순히 집합으로 나눌 수 없어 불가능하다.

따라서 3중 루프 방식을 떠올렸다.(i에서 j로 갈 수 있다면, j에서 갈 수 있는 k에 대해 i에서 k로 갈 수 있다는 것)

나중에 보니 이 방식이 플로이드-워셜 알고리즘이었다는걸 깨달았다.(유사하다고 생각하긴 했다)

다만, 실제 플로이드-워셜 알고리즘을 적용할 경우에는 갈 수 없는 거리 값들을 최대로 만들어주는 과정이 필요했는데,

그 과정 대신에 갈 수 있느냐를 체크해서 적용하다보니 한 번 더 반복해야하는 아쉬움이 남았다.