백준 11403(경로 찾기)

jh Seo·2022년 11월 14일

DFS 백준 한번에 못 푼 문제

백준

목록 보기

77/194

개요

백준 11403: 경로찾기

입력
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.
출력
총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

접근방법

그래프를 생성해서 간선을 연결해주는 식으로 짜고, 0부터 N-1 범위의 변수 i를 매개변수로 dfs(i)를 실행한다.
그후 각 dfs에서 true가 나온 값은 i번째에서 해당값으로 도달할 수 있다는 뜻이므로
해당 true값으로 답배열인 ansGraph를 채운다.
-> 이 방식으로는 무조건 첫값이 true가 나와서 (i,i)좌표는 다 1이 나온다.
첫번째 값을 false로 해야하는데 어떻게 할질 모르겠다.
하지만 인터넷에서 index값을 매개변수로 전달해주는걸 보고 깨달았다.

코드

#include<iostream>
#include<vector>

using namespace std;
int N = 0;
class graph {
public:
	int Nodes;
	//인접리스트
	vector<vector<int>> adj;
	//방문했는지 여부
	vector<bool> visited;

	graph(int n) :Nodes(n) {
		adj.resize(n);
		visited.resize(n);
	}


	/// <summary>
	/// 방향그래프의 간선추가 하는 함수. 한 방향만 추가한다.
	/// </summary>
	/// <param name="u"></param>
	/// <param name="v"></param>
	void AddEdge(int u, int v) {
		adj[u].push_back(v);
	}

	//매개변수는 각각 u부터 dfs시작, 맨처음 인덱스가 뭔지, 맨처음 재귀함수인지
	void dfs(int u,int firstIndex,bool first) {
		//방문했다면 return
		if (visited[u]) return;
		//만약 첫번째 인덱스이고, 맨처음이면
		if (u == firstIndex && first) {
			//visited[u]를 false로 해놔야한다.
			visited[u] = false;
		}
		//첫밴째 인덱스지만, 맨처음이 아니라면
		else if (u == firstIndex && !first) {
			//true로 바꿔야한다.
			visited[u] = true;
		}
		//첫번째인덱스가 아니라면 true로 설정
		else visited[u] = true;
		//노드u와 인접한 모든 노드에 대해
		for (int elem : adj[u]) {
			//방문 안한 노드라면
			if (!visited[elem]) {
				//해당 노드, 맨처음 인덱스값, 맨처음이아니라는 의미로 false
				dfs(elem,firstIndex,false);
			}	
		}
	}

};
graph* g;
void input() {

	cin >> N;
	g=new graph(N);
	int tmp = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> tmp;
			if (tmp == 1) {
				g->AddEdge(i, j);
			}
		}
	}

}
void solution() {
	for (int i = 0; i < N; i++) {
			//매 반복문마다 방문 배열을 false로 초기화
			fill(g->visited.begin(), g->visited.end(), false);
			g->dfs(i,i,true);
			//i번째일때 방문배열을 다 출력
			for (int j = 0; j < N; j++) {
				cout << g->visited[j]<<' ';
			}
			//endl
			cout << '\n';
	}
}

int main() {
	input();
	solution();
}

dfs함수 더 간결하게 짠 코드

#include<iostream>
#include<vector>

using namespace std;
int N = 0;
class graph {
public:
	int Nodes;
	//인접리스트
	vector<vector<int>> adj;
	//방문했는지 여부
	vector<bool> visited;

	graph(int n) :Nodes(n) {
		adj.resize(n);
		visited.resize(n);
	}


	/// <summary>
	/// 방향그래프의 간선추가 하는 함수. 한 방향만 추가한다.
	/// </summary>
	/// <param name="u"></param>
	/// <param name="v"></param>
	void AddEdge(int u, int v) {
		adj[u].push_back(v);
	}
	
	//맨처음 u에 도달했을때 u노드에 visited체크 안하는 함수
	void dfs(int u) {
		//u와 인접한 노드들 elem
		for (int elem : adj[u]) {
			//elem에 방문 안했다면
			if (!visited[elem]) {
				//방문함 체크
				visited[elem] = true;
				//elem노드에 대해 재귀
				dfs(elem);
			}
		}
	}

};
graph* g;
void input() {

	cin >> N;
	g=new graph(N);
	int tmp = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> tmp;
			if (tmp == 1) {
				g->AddEdge(i, j);
			}
		}
	}

}
void solution() {
	for (int i = 0; i < N; i++) {
			//매 반복문마다 방문 배열을 false로 초기화
			fill(g->visited.begin(), g->visited.end(), false);
			//g->dfs(i,i,true);
			g->dfs(i);
			//i번째일때 방문배열을 다 출력
			for (int j = 0; j < N; j++) {
				cout << g->visited[j]<<' ';
			}
			//endl
			cout << '\n';
	}
}

int main() {
	input();
	solution();
}