BOJ 11403 경로 찾기

📎Problem Link

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

11403번: 경로 찾기

📋 문제 정리

• 가중치 없는 방향 그래프 G
• 입력 첫째줄에는 정점의 개수 N(1 ≤ N ≤ 100)
• 입력 둘째줄부터 N개의 줄에는 그래프 인접 행렬 입력
• i번째 줄의 j번째 숫자가 1이라면 i에서 j로가는 경로가 있다는 뜻! 다른 node를 거쳐가는 것도 포함
• i번째 줄의 j번째 숫자가 0이라면 i에서 j로가는 경로가 없다는 뜻!

 

📌 예제 1

• 인접 행렬
                                                    
  

  0	1	0
  0	0	1
  1	0	0

  이 인접 행렬 표를 눈에 쉽게 나타내면 다음과 같다.
  
  

  

  
   
  
  
  
  
  
  
• 결과
  
  

  1	1	1
  1	1	1
  1	1	1

  
  

📌 예제 2

• 인접 행렬
  
  

  0	0	0	1	0	0	0
  0	0	0	0	0	0	1
  0	0	0	0	0	0	0
  0	0	0	0	1	1	0
  1	0	0	0	0	0	0
  0	0	0	0	0	0	1
  0	0	1	0	0	0	0

  이 인접행렬을 쉽게 나타내면 다음과 같다.
  

  

• 결과
  
  

  1	0	1	1	1	1	1
  0	0	1	0	0	0	1
  0	0	0	0	0	0	0
  1	0	1	1	1	1	1
  1	0	1	1	1	1	1
  0	0	1	0	0	0	1
  0	0	1	0	0	0	0

---

💻 Code

 

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

int main() {
	int Node;
	int matrix[101][101] = { 0 };

	cin >> Node;

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


	for (int k = 0; k < Node; k++) { //플로이드-와샬 알고리즘
		for (int i = 0; i < Node; i++) {
			for (int j = 0; j < Node; j++) {
				if (matrix[i][j] == 0)
					matrix[i][j] = (matrix[i][k] && matrix[k][j]);
			}
		}
	}

	for (int i = 0; i < Node; i++) { //결과 출력
		for (int j = 0; j < Node; j++) {
			cout << matrix[i][j] << " ";
		}
		cout << endl;
	}
}

이 문제도 1년 전에 BFS 방식으로 풀었던 문제다. 하지만 여러모로 BFS보다 플로이드-와샬 알고리즘을 이용해 문제를 푸는 것이 코드면에서도 깔끔할 것 같다는 생각이 들었다. 삼중 for문을 돌려야한다는 것이 시간면에서 꺼림칙했지만 이번에는 플로이드 와샬로 작성해보기로 했다.

먼저 matrix에 인접 행렬을 작성한다. 그 후, 인접 행렬에서 0인 부분만 살펴본다.

예를 들어 matrix[1][2]가 0이라고 가정하자. 이 뜻은 1에서 2로 가는 경로가 있는지 아직 살펴보지 않았음을 뜻한다. 만약 1에서 0으로 가는 간선이 있고(matrix[1][0]이 1), 0에서 2로 가는 간선이 존재한다면(matrix[0][2]가 1) 1에서 0을 거쳐 2로 갈 수 있다는 뜻이므로 &연산에 의해 matrix[1][2]에 1이 입력된다.

 

---

1년 전에 BFS로 작성했던 것에 비해 메모리면에서 44KB나 줄은 것을 볼 수 있다. (코드도 꽤 줄었네!) 다른 사람들은 어떻게 나오나 슬쩍 봤는데 나랑 똑같이 메모리가 2020KB지만 속도가 4ms인 경우도 꽤 있었다. 앞으로 속도면에서도 줄어보려고 노력을 더 해봐야겠다.