[백준 11403] 경로 찾기

stack으로 DFS연습하려고 품

근데 플로이드 워셜 알고리즘으로 푸는 방법도 있다고 한다.

그건 일단 나중에

오늘 술마심 ㅇㅇ

 

여기서 내가 막판에 놓친게 

stack<int> st;
st.push(start);
ans[node][start] = 1;

 

여기서 ans[node][start] = 1 쓰는걸 안해서 결과인 ans 배열에

기존으로 입력된 arr 배열에 1이 들어간 부분들을 표시 안되게 했다. 주의요망 ㅇㅇ

 

---

#include <iostream>
#include <stack>

#define SIZE 101

using namespace std;

int N;
int arr[SIZE][SIZE];
int ans[SIZE][SIZE];

void DFS(int node, int start) {

	stack<int> st;
	st.push(start);
	ans[node][start] = 1;

	while (!st.empty()) {
		int cur = st.top();
		st.pop();

		for (int i = 1; i <= N; i++) {
			if (arr[cur][i] && ans[node][i]==0) {
				ans[node][i] = 1;
				st.push(i);
			}
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= N; k++) cin >> arr[i][k];
	}
	
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= N; k++) {
			if(arr[i][k]) DFS(i,k);
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= N; k++) {
			cout << ans[i][k] << " ";
		}
		cout << "\n";
	}

	return 0;
}