[알고리즘] 인접행렬과 경로탐색 기초 (그래프 DFS: Depth First Search)

# 인접 행렬 (隣接行列, adjacency matrix)

인접 행렬은 노드들이 간선으로 어떻게 연결되어 있는지 나타내는 정사각 행렬입니다.

위 그림을 말로 설명하면

노드 1은 노드 2로 연결되었고,

노드 1은 노드 3으로 연결되었고,

노드 1은 노드 4로 연결되었고,

노드 2는 노드 4로 연결되었고,

노드 3은 노드 4로 연결되었고,

노드 4는 노드 5로 연결되어있습니다.

 

이 것을 행렬로 표현하면

행의 1,2,3,4,5는 출발 노드로

열의 1,2,3,4,5는 도착 노드로 하여

다음과 같습니다.

 

0은 연결되지 않았음

1은 연결되었음을 표현합니다.

 

1행 2열은 노드 1에서 노드 2로 연결되었음을,

1행 3열은 1에서 3으로 연결되었음을,

1행 4열은 1에서 4로 연결되었음을,

2행 4열은 2에서 4로 연결되었음을,

3행 4열은 3에서 4로 연결되었음을,

4행 5열은 4에서 5로 연결되었음을 말합니다.

 

 

 

따라서 아래와 같이 입력이 들어온다면.

4 6    // 노드 갯수 4, 간선 갯수 6

1 2    // 밑으로는 간선 갯수 6줄 만큼 노드간의 이동 방향

1 3

1 4

2 4

3 4

4 5

 

아래와 같이 코드로 입력받아 2차 배열로 표현할 수 있습니다.

#include <stdio.h>
using namespace std;

int am[6][6];	// 0으로 초기화하기 위해 전역변수로 선언.

int main(){
	int n, m, a, b;
	scanf("%d %d", &n, &m);
	
    // 인접 행렬 입력
	for(int i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		am[a][b]=1;
	}
	
    // 인접 행렬 출력
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			printf("%d ", am[i][j]);
		}
		printf("\n");
	}
	return 0;
}

출력결과
0 1 1 1 0
0 0 0 1 0
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0

 

# 무방향 그래프

이렇게 양방향으로 이동할 수 있는 그래프는 무방향 그래프라고 합니다.

 

 

노드1에서 노드 2로 입력이 들어온다면

양 방향 통행이 가능하다는 뜻으로

1행 2열과 거꾸로인 2행 1열에도 1을 넣어줍니다.

 

특징이라면 오른쪽 아래를 향하는 사선을 기준으로

대칭된 모양을 가진다는 것을 볼 수 있습니다.

 

 

 

 

 

 

#include <stdio.h>
using namespace std;

int am[6][6];

int main(){
	freopen("input.txt", "rt", stdin);
	int n, m, a, b;
	scanf("%d %d", &n, &m);
	
	for(int i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		am[a][b]=1;
		am[b][a]=1;	// 반대방향 간선 표시. 이 외 나머지 코드는 방향 그래프와 같습니다.
	}
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			printf("%d ", am[i][j]);
		}
		printf("\n");
	}
	return 0;
}

출력결과
0 1 1 1 0
1 0 0 1 0
1 0 0 1 0
1 1 1 0 1
0 0 0 1 0

# 가중치 방향 그래프

단순히 방향의 유무가 아니라

간선을 통과하는데 비용이 있을 수 있습니다.

 

위 그래프는 노드 1에서 노드2로 가는데 비용이 1이 들고,

노드 2에서 노드4로 가는데 비용이 4가 들고,

노드 4에서 노드5로 가는데 비용이 5가 든다는 의미입니다.

여기에서 비용은 임의의 숫자일 뿐 노드나 간선사이의 연관관계는 없습니다.

 

이렇게 비용이 있는 그래프를 간선에 가중치가 있다해서 가중치 방향 그래프라고 합니다.

 

이것을 인접행렬로 표현하려면 0과 1이 아닌 가중치 수치를 넣어주면 됩니다.

 

이렇게 만들어진 인접행렬을 통해

값이 0인 간선은 통행할 수 없는 경로이고,

1이상인 곳은 통행할 수 있으며, 

그 값이 가중치임을 알 수 있습니다.

 

 

 

 

 

 

 

 

 

#include <stdio.h>
using namespace std;

int am[6][6];

int main(){
	int n, m, a, b, c; // 가중치를 위해 변수 c 추가
	scanf("%d %d", &n, &m);
	
	for(int i=1; i<=m; i++){
		scanf("%d %d %d", &a, &b, &c);	
		am[a][b]=c;	// 이제 1이 아닌 가중치 값을 대입해줍니다.
	}
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			printf("%d ", am[i][j]);
		}
		printf("\n");
	}
	return 0;
}

출력결과
0 1 2 3 0
0 0 0 4 0
0 0 0 6 0
0 0 0 0 5
0 0 0 0 0

 

# 인접행렬의 경로탐색

노드의 수 n, 간선의 수 m. 그 다음부터 m줄에 걸쳐 연결 정보가 주어집니다.

이 방향 그래프에서 1노드에서 n노드까지 이동할 수 있는 총 가짓수를 구해야합니다.

단, 1<=n<=20

입력 예
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

 

이 입력을 그래프로 그리면 아래와 같습니다.

노드 1에서 노드5로 가는 경로는

1 2 3 4 5

1 2 5

1 3 4 2 5

1 3 4 5

1 4 2 5

1 4 5

이렇게 총 6가지입니다.

 

 

 

 

 

그래서 가짓 수인 6을 출력하면 됩니다.

출력 예
6

 

#include <stdio.h>
using namespace std;

// 노드의 포함 여부를 체크할 ch변수
// 노드1에서 노드5로 도착하는 경우를 카운트할 cnt변수
// 그리고 재귀함수에서 노드 갯수를 사용하기에 n변수를 전역변수로 선언
int map[21][21], ch[21], cnt, n;

void D(int v){

    // 현재 노드가 n이라면 도착한 것이므로 cnt++하고 함수 종료합니다.
    if(v==n){
        cnt++;
    }else{
        for(int i=1; i<=n; i++){
			
            // 다음으로 가야할 노드 i가 갈 수 있는 경로이고 &&
            // 아직 가본적 없는 노드라면 이동합니다.
            if(map[v][i]==1 && ch[i]==0){
				
                // 현재 탐색중인 경로에 포함한다는 의미로 체크
                ch[i]=1;
				
                // 다음 경로로 재귀 함수 탐색
                D(i);
                
                // 현재 경로 탐색이 끝난 후 다음 경로 탐색을 위해 체크 해제
                ch[i]=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;
	}
    
	// 노드1은 출발지이기 때문에 방문 체크하고 시작합니다.
	ch[1]=1;
	
	// 노드 1을 뜻하는 1을 인수로 재귀함수를 호출합니다.
	D(1);
    
	printf("%d", cnt);
	return 0;
}