[Algorithm] 인접행렬(가중치 방향그래프)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

ㅇ 인접 행렬 

  - 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각 행렬

  - 정점(node, vertex)과 간선의 집합

ㅇ 무방향 그래프(Undirected Graph)

  - 방향이 없는 간선

  - 간선은 양방향 관계를 나타내며, 각 간선은 양방향으로 진행

  - 행이 출발 정점, 열이 도착 정점

  - 무방향 그래프 인접 행렬

ㅇ 방향 그래프(Directed Graph)

  - 방향이 있는 간선

  - 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행

  - 방향 그래프 인접 행렬

ㅇ 가중치 방향 그래프

   - 방향 그래프에 가중치가 부여된 그래프

   - 가중치 방향 그래프 인접 행렬

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include<stdio.h> #include<vector> #include<algorithm>   using namespace std;   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; } Colored by Color Scripter

cs

보통 대회에서는 아래 입력 형식과 같이

정점의 개수와 간선의 개수가 주어지고

출발 정점, 도착 정점, 가중치 이렇게 주어진다고 한다.

6 9 

1 2 7

1 3 4

..

line 14~17) 2차원 배열에서 출발 정점, 도착 정점 위치에 가중치를 저장한다.

line 19~24) 가중치를 저장한 2차원 배열의 정보를 출력

#. Result

  - Input --------------------------------------------------------

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 

------------------------------------------------------------------

  - Output --------------------------------------------------------

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

------------------------------------------------------------------