[Python Algorithm] 완전탐색(DFS) - 인접행렬(가중치 방향그래프)

> 완전탐색 - 백트랙킹, 상태트리와 CUT EDGE / DFS 기초 

 

 

 

 

📖 문제 : 인접 행렬 (가중치 방향 그래프)

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

 

 

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

 

출력설명
인접행렬을 출력하세요.

 

입력예제 1

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

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

 

import sys

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()

 

⭐️ Point ! ⭐️

• 인접 행렬은 행 -> 열로 이동한다고 생각하면 됨.
    1 2 3 4 5
  1   1             -> 1 의 의미는 1에서 2로 갈 수 있다 는 의미 
  2
  3
  4
  5

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이