[백준] 11403-경로찾기(C++)

문제링크: https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

기본적인 dfs, bfs 문제였습니다.

 

숫자범위도 n=100까지이고 dfs를 사용해도 지장이 없을 것 같아 직관적인 dfs 알고리즘을 사용해 구현하였습니다.

 

 

반복문을 통해 arr[i][j]=1일땐 dfs를 호출해 해당줄에서 방문이 가능한 도시를 체크합니다.

방문 이후에는 통합시켜주며 마무리합니다.

 

#include <iostream>
using namespace std;
int n = 0;
int arr[101][101] = { 0 };
bool visited[101];

void dfs(int y, int x) {
	
	for (int i = 1; i <= n; i++) {
		if (arr[x][i] == 1 && !visited[i]) {
			visited[i] = 1;
			dfs(y, i);
		}	
	}
	
}

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

		for (int j = 1; j <= n; j++)
			visited[j] = 0;

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

		for (int j = 1; j <= n; j++) {
			if (visited[j] == 1)
				arr[i][j] = 1;
		}
	}
	
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << arr[i][j] << ' ';
		}
		cout << endl;
	}
}

 

밑에는 dfs, bfs 를 안쓰고 O(n^3)만에 끝내는 컴팩트한 방법입니다.

#include <iostream>
using namespace std;
int main(){
	int n; 
	cin >> n;
	bool map[101][101] = {};
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++) cin >> map[i][j];
	}
	for(int k = 0; k < n; k++){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(map[i][k] && map[k][j]) map[i][j] = true;
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++) cout << map[i][j] << ' ';
		cout << '\n';
	}
}