[BOJ] 11403번 경로 찾기 - C++

문제

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

11403번: 경로 찾기

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

 

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

---

풀이

입력 데이터를 바탕으로 그래프를 그려서 i 노드에서 j로 가는 경로가 있으면 1, 없으면 0으로 채워주는 문제.

문제 이해를 위해 예제 입력 2를 바탕으로 그래프를 그려보면

행/열	0	1	2	3	4	5	6
0	0	0	0	1	0	0	0
1	0	0	0	0	0	0	1
2	0	0	0	0	0	0	0
3	0	0	0	0	1	1	0
4	1	0	0	0	0	0	0
5	0	0	0	0	0	0	1
6	0	0	1	0	0	0	0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

이렇게 행렬에 대응하여 그래프가 그려지는 것을 확인할 수 있다.

 

문제 유형에는 플로이드 와샬 방법이 적혀있지만 나는 DFS로 풀었다

1. 각 노드별 DFS 실행

2. 노드별 DFS가 끝나면 방문 결과에 따라 원본 배열에 1 체크

 

평소 DFS 구조와 다른 것은 노드에서 최초로 DFS를 실행할 때, 다시 최초 실행 지점으로 돌아와야만 최초노드 -> 최초노드 경로가 있다는 뜻이므로, 최초 노드를 처음 방문할 때 visited를 true로 만들어주면 안된다.

그래서 방문할 다음 노드부터 visited를 true로 체크해주는 방식으로 해결하였다.

 

노드별로 DFS를 실행할 때, visited 배열을 초기화해야하므로 cstring헤더의 memset을 이용하여 false로 초기화해준 뒤 다시 DFS를 돌려준다.

---

코드

#include <iostream>
#include <cstring>
const int MAX = 101;
using namespace std;

int arr[MAX][MAX];
bool visited[MAX];

int n;

void dfs(int v) {
	for (int i = 0; i < n; i++) {
		if (!visited[i] && arr[v][i]) {
			//최초 시작 노드는 방문을 체크해주면 안되니 
			//방문 여부를 그 다음 노드부터 체크하도록 해줌
			visited[i] = true;
			dfs(i); 
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		memset(visited, false, MAX);
		dfs(i);
		for (int j = 0; j < n; j++) {
			if (visited[j]) arr[i][j] = 1;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << arr[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}

 

---

삽질 & 개선점

문제를 똑바로 읽자ㅠㅠ 방향 그래프인데 무방향 그래프인줄 알고 양쪽으로 값을 넣어줘버리고 한참 삽질했다..

그래프 관련 문제를 풀 때는 꼭 방향 그래프인지 무방향 그래프인지 구분하고 문제를 풀 것!