[개념] 인접 행렬(가중치 방향그래프) / c / 제한시간 없음

▣ 입력설명

- 아래 그림과 같은 그래프 정보를 인접행렬로 표현해보세요.

 

▣ 입력설명

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

 

▣ 출력설명

- 인접행렬을 출력하세요.

 

▣ 입력 예시

6 9 1 2 7 1 3 4 2 1 2 2 3 5 2 5 5 3 4 5 4 2 2 4 5 5 6 4 5

 

▣ 출력 예시

0 7 4 0 0 0 2 0 5 0 5 0 0 0 0 5 0 0 0 2 0 0 5 0 0 0 0 0 0 0 0 0 0 5 0 0

 

<코드>

#pragma warning(disable:4996)
#include<stdio.h>

int map[21][21];
int main() {
	int n, m, a, b, c, i, j;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		map[a][b] = c;
	}
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			printf("%d ", map[i][j]);
		}
		printf("\n");
	}
	return 0;
}

이 문제에서 인접행렬이란 '그래프'의 자료 구조를 설명한다.

 

그래프는 크게 '무방향 그래프', '방향 그래프', '가중치 방향그래프' 이렇게 3가지로 구분 지을수 있다.

 

'무방향 그래프'는 각 정점(vertex)을 잇는 간선(edge)이 가르키는 방향이 없는것이다.

 

'방향 그래프'는 각 정점을 잇는 간선이 가르키는 방향이 있는 것이다.

 

'가중치 방향그래프'는 각 정점을 잇는 간선이 가르키는 방향과 값이 있는 것이다.

 

위 코드를 보면 a,b는 정점(vertex)를 알려주고 c는 간선(edge)이 가지는 가중치 값을 나타낸다.

 

이 개념과 나중에 '인접 리스트'는 DFS 또는 BFS를 푸는데 기본적인 문제 접근을 도와준다.