[알골90제] 64번-경로탐색 DFS(노드, 간선) / 65번미로탐색 DFS(인접행렬)

64번 - 경로탐색 DFS(노드, 간선)

 

* 문제 

 

방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요.

 

첫째줄: 정점의 수 N(1<=N<=20)와 간선의 수 M이 주어진다. 그 다음부터 M줄에 걸쳐 연결정보가 주어진다.

for문은 간선의 수만큼 생김(어떤 정점들끼리 연결되었는지 입력해야하기 때문)

 

입력:

5 9 1 2 1 3 1 4 2 1 2 3 2 5 3 4 4 2 4 5 

출력:

6

 

=> 1에서 5까지 가는 경로의 가지 수 출력

//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;

}

 

 

 

65번 - 미로탐색 DFS(인접행렬)

 

* 문제 

 

자연수 N이 주어지면 7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작 성하세요.  출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽 이고, 0은 통로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면 위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다.

 

//65번 - 미로탐색(DFS)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int map[8][8], check[8][8], cnt = 0;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

void DFS(int x, int y) {

	int xx, yy;

	if (x == 7 && y==7) {
		cnt++;
	}
	else {
		for (int i = 0; i < 4; i++) {
			xx = x + dx[i];
			yy = y + dy[i];
			if (xx < 1 || xx>7 || yy < 1 || yy>7) continue;
		
			if (map[xx][yy] == 0 && check[xx][yy] == 0) {
				check[xx][yy] = 1;
				DFS(xx, yy);
				check[xx][yy] = 0;

			}
		}
	}
}

int main() {

	//freopen("input.txt", "rt", stdin);
	for (int i = 1; i <= 7; i++)
		for (int j = 1; j <= 7; j++)
			scanf("%d", &map[i][j]);

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

	return 0;
}