[알골90제] 66번 - 경로찾기:DFS (인접리스트로 풀기/64번과 문제 동일)

64번은 인접행렬로 풀었지만 66번에서는 인접 리스트로 경로를 찾아보자.

 

방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프 로그램을 작성하세요. 
▣ 입력설명 첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연 결정보가 주어진다.
▣ 출력설명 총 가지수를 출력한다.

 

 

* 인접리스트 

 

 

1번 정점과는 2번, 3번, 4번 정점과 연결되어 있다는 뜻

2번 정점과는 1번, 5번 정점과 연결되어 있어 1번과 5번에 갈 수 있다는 뜻

 

n이 1000정도 되어서 map[1000][1000] 정도 되면 i가 1부터 1000까지 for문이 돌아야함

 

- 인접리스트는 map만 1000개 만들어주고 연결만 해주면 됨

map[1].size() 하면 3을 리턴함 

즉, for문이 map의 size만큼만 돌면 됨

=> 즉 인접행렬로 하는 것 보다 훨씬 효율적임

 

mam[v][i]

i가 1이면 2번

i가 2면 3번

i가 3이면 4번

 

쉽게 접근할 수 있음

 

 

 

 

 

인접리스트

// 66번 - 인접리스트로 경로찾기 (64번과 동일한 문제)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
using namespace std;

int n, ch[30], cnt = 0;
vector<int> map[30];

void DFS(int v) {

	if (v == n) cnt++; 
	else {
		for (int i = 0; i < map[v].size(); i++) {
		
			if (ch[map[v][i]] == 0) {//방문안한것
				ch[map[v][i]] = 1;
				DFS(map[v][i]);
				ch[map[v][i]] = 0;
			}
		}
	}
}


int main() {

	//freopen("input.txt", "rt", stdin);

	int m, a, b;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &a, &b);

		//인접리스트 만듬
		map[a].push_back(b);
	}

	ch[1] = 1;
	DFS(1);
	printf("%d\n", cnt);


}

 

 

 

인접행렬 (64번)

 

//64번 - 경로 탐색 DFS

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int map[30][30], ch[30], cnt=0, n;

void DFS(int v) {

	if (v == n) {
		cnt++;
	}
	else {
		for (int i = 1; i <= n; i++) {
			if (map[v][i] == 1 && ch[i] == 0) {
				ch[i] = 1;
				DFS(i);
				ch[i] = 0;
				//왜 체크를 풀어야 하나?
				//호출하고 되돌아 올때 0으로 해줘야 되돌아 거기 갈 수 있는 것
			}
		}
	}	
}

int main() {

	int m, a, b;
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= m; i++) {
		
		scanf("%d, %d", &a, &b);
		map[a][b] = 1;
	}

	ch[1] = 1;
	DFS(1);
	printf("%d\n", cnt);
	return 0;

}