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

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

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

 

아래 그림과 같은 가중치 방향그래프를 인접 행렬로 표현하는 프로그램을 작성하시오.

 

가중치 방향그래프

 

*입력 설명

첫 번째 줄에는 노드의 수 N(2 ≤ N ≤ 20)과 간선의 수 M이 주어진다.

그 다음줄 부터 M줄에 걸쳐 연결정보와 거리비용이 주어진다.

 

*출력 설명

가중치 방향그래프를 표현한 인접 행렬을 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_54.txt', 'rt')
n, m = map(int, input().split())
g = [[0] * (n+1) for _ in range(n+1)]

for i in range(m):
    a, b, c = map(int, input().split())
    g[a][b] = c

for i in range(1, n+1):
    for j in range(1, n+1):
        print(g[i][j], end=' ')
    print()
    
'''
출력 :
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 

'''

 

input_54.txt(입력)

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

 

 

중요내용

1. 가중치 방향그래프는 노드와 간선으로 이루어져있다.
2. 가중치 방향 그래프는 노드와 노드를 연결하는 간선에 방향표시가 있으며, 해당 간선에 가중치 값이 존재하는 그래프이다.
3. 인접 행렬의 결과는 2차원 리스트에 저장한다. (2차원 리스트와 이중 for문 활용)
4. 인접 행렬은 항상 행에서 열로 이동한 결과 값을 보여준다. (행번호 --> 열번호)
5. 인접 행렬에 값을 부여할 때 노드의 개수만큼 반복문이 실행되어야 한다. (ex. for i in range(m):)