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

안녕하세요.

오늘은 백준 11403번: 경로 찾기(링크)  문제를 풀어보려고 합니다.

 

문제

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

 

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

 

출력

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

 

예제 입력

// 예제 입력 1
3
0 1 0
0 0 1
1 0 0

// 예제 입력 2
7
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
1 1 1
1 1 1
1 1 1

// 예제 출력 2
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

 

제한

시간 제한: 1초

메모리 제한: 256MB

 

---

풀이

BFS, 플로이드-와샬 같은 최단경로 알고리즘 등 다양하게 풀 수 있는데, 저 같은 경우 DFS로 풀었습니다.

 

먼저 인접 행렬로 들어오는 그래프를 vector를 사용해서 저장하고, dfs를 함수를 작성해서 불러줍니다.

 

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
vector<int> v[101];
bool visit[101] = {false};

int main() {
	int n;
	cin >> n;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			int a;
			cin >> a;
			if(a){
				v[i].push_back(j);
			}
		}
	}
	for(int i=0; i<n; i++){
		vector<int> hist;
		memset(visit,false,sizeof(visit));
		dfs(i,i,hist);
	}
	return 0;
}

 

dfs함수는 기본적인 틀에서 약간의 변형만 해주면 되었는데,  dfs가 시작되는 지점, 맨 처음에 시작한 지점, 그리고 dfs를 하며 방문했던 노드를 저장할 벡터. 이렇게 총 3가지의 매개변수를 두었습니다.

 

void dfs(int start, int from, vector<int>& history)

 

 

dfs에서는 먼저 이전 노드들이 저장된 history 벡터의 있는 값을 가져옵니다. 해당 벡터의 값에서 현재 dfs를 시작하는 점인 start 사이에는 경로가 있다는 의미이므로 route[history[i]][start] = true;로 해줍니다.

 

하나 예시를 들어 0→1→2 로 구성된 그래프가 있다고 생각해 보겠습니다.

• 0에서 시작했을 때
  • 0번 노드 방문 처리. visit[0] = true;
  • 1로 가기전 history 벡터에 0을 넣는다. hitstory.push_back(0);
  • 이후 dfs(1,0,history) 실행
• history의 있는 값을 가져와서 route업데이트. 여기서는 0이 들어가 있으니
  • route[0][1] = true;
  • visit[1] = true;
  • 이후 history에 1넣는다.  hitstory.push_back(1);
  • 다시 dfs(2,0,hisotry).
• 또 다시 history에 있는 값을 가져와서 route 업데이트.
  • route[0][2] = true;
  • route[1][2] = true;
  • 이후 history, dfs 작업 ~
• 위 과정을 경로가 존재하는 노드에 대해서 진행

하고 나서 여기서 백트래킹 기법이 들어갑니다.

 

dfs를 하기 전 history에 start를 넣었고 이후 다른 정점으로 가기전에 history에 있는 것을 빼주어서 중복으로 들어가지 않게 해줍니다.

정답

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
bool route[101][101] = {{false}};
vector<int> v[101];
bool visit[101] = {false};
void dfs(int start, int from, vector<int>& history){
	// 이전에 방문한 노드들 포함 route 업데이트
	for(int i=0; i<history.size(); i++){
		route[history[i]][start] = true;
	}
	visit[start] = true;
	for(int i=0; i<v[start].size(); i++){
		int next = v[start][i];
		// 다시 원래 출발 지점으로 돌아왔으면 route 업데이트
		if(next==from){
			route[from][next] = true;
		}
		if(visit[next]) continue;
		history.push_back(start);
		dfs(next,from,history);
		history.pop_back();
	}
}

int main() {
	int n;
	cin >> n;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			int a;
			cin >> a;
			if(a){
				v[i].push_back(j);
			}
		}
	}
	for(int i=0; i<n; i++){
		vector<int> hist;
		memset(visit,false,sizeof(visit));
		dfs(i,i,hist);
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cout << route[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}

---

이렇게 해서 백준 11403번 경로찾기 문제를 풀어보았습니다.

 

댓글로 질문을 남기시면 성실히 답해드리겠습니다

 

감사합니다!