백준 11403 경로 찾기

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 정점 N개를 가지는 그래프의 인접 행렬을 입력 받고  정점 i에서 j로 갈 수 있는 경우가 있다면 1 그렇지 않다면 0으로 나타나는 행렬을 출력해야 합니다.

 

저는 이 문제를 bfs를 통해서 풀었습니다. i에서 j로 갈수 있는경우가 있는 경우 bfs 함수로 들어가서 visited[i][j] 를 1로 만들어주고 그후 j에서 다른 위치로 갈 수 있는지를 확인후 예를들어 j 에서 k로 갈 수 있다면 i -> j -> k 의 경로를 통해 i에서 k로 갈 수 있으므로 visited[i][k]를 1로 만들어 주는 식으로 i에서 어떤 다른 경로를 거쳐서 어떠한 경로로 갈 수 있는 모든 경우를 탐색하고 나온 뒤 또 다른 i에서 j로 갈 수 있는 경우를 동일한 방식으로 bfs를 통해서 찾았습니다.

 

다음은 코드입니다.

 

심심해서 dfs로도 한번 풀어봤습니다. dfs가 더 짧고 큐를 사용 안하니 더 효율적일 것 같습니다. 그리고 이 문제 같은 경우 방문 할 수 없는 0으로 표시된 지점들은 사실 필요가 없기 때문에 행렬로 모두 받는 것 보다 인접 리스트 형식으로 벡터 배열을 사용해 각 정점들이 갈 수 있는 점들을 저장해서 dfs나 bfs를 돌리는 것이 훨씬 효율적일것 같습니다..

 

 

 #include <iostream>
#include <queue>

using namespace std;

int adj[101][101];
int visited[101][101];
queue<pair<int, int>> q;
int N;

void bfs(int a, int b) {
	
	visited[a][b] = 1;
	q.push(make_pair(a, b));
	
	while(!q.empty()) {
		
		for(int i = 0; i < N; i++)
			if(adj[q.front().second][i] && !visited[a][i]) {
				visited[a][i] = 1;
				q.push(make_pair(q.front().second, i));
			}
		q.pop();
	}
}



int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N; 
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			cin >> adj[i][j];
			
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			if(adj[i][j])
				bfs(i, j);
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++)
			cout<<visited[i][j] << ' ';
			cout<<'\n';
		}
	return 0;
}

 

#include <iostream>
#include <queue>

using namespace std;

int adj[101][101];
int visited[101][101];
queue<pair<int, int>> q;
int N;

void dfs(int a, int b) {
	
	visited[a][b] = 1;
		
	for(int i = 0; i < N; i++)
		if(adj[b][i] && !visited[a][i]) {
			dfs(a, i);
		}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N; 
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			cin >> adj[i][j];
			
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			if(adj[i][j])
				dfs(i, j);
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++)
			cout<<visited[i][j] << ' ';
			cout<<'\n';
		}
	return 0;
}

 

하는김에 벡터를 이용해 인접리스트 형식으로도 한번 구현을 해보았습니다. 다음은 코드입니다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> v[101];
int visited[101][101];
int N;

void dfs(int a, int b) {
	
	visited[a][b] = 1;
		
	for(int i = 0; i < v[b].size(); i++)
		if(!visited[a][v[b][i]]) {
			dfs(a, v[b][i]);
		}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N; 
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++) {
			int x;
			cin >> x;
			if(x) {
				v[i].push_back(j);
			}
		}
			
	for(int i = 0; i < N; i++)
		for(int j = 0; j < v[i].size(); j++)
			dfs(i, v[i][j]);
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++)
			cout<<visited[i][j] << ' ';
			cout<<'\n';
		}
	return 0;
}