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

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

 

▣ 입력설명

첫째 줄에는 정점의 수 N(2<=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

---

내가 쓴 코드

#인접행렬
import sys
sys.stdin = open("input.txt",'rt')
input = sys.stdin.readline


N,M = map(int, input().split())

#2차원배열(행렬 생성)
rows = cols = N
matrix = [[0 for j in range(cols)] for i in range(rows)]


for _ in range(M):
    i,j,weight = map(int, input().split())
    #인덱스니까 1 빼주깅
    matrix[i-1][j-1] = weight

#출력
for row in matrix:
    for col in row:
        print(col, end=' ')
    print()

 

모범답안: 무방향 인접행렬

#모범답안 - 무방향 인접행렬 코드
import sys
sys.stdin = open("input.txt",'rt')
input = sys.stdin.readline

#인덱스를 노드 자체로 쓰기 위해 n+1 * n+1 행렬 선언
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] = 1
    g[b][a] = 1

#인덱스 1부터 출력
for i in range(1, n+1):
    for j in range(1, n+1):
        print(g[i][j], end=' ')
    print()

 

모범답안: 방향 인접행렬 코드

#모범답안 - 방향 인접행렬 코드
n, m = map(int, input().split())
g = [[0 for _ in range(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()

 

느낀점

1. 2차원 배열 선언할 때
matrix = [[0]*N]*N
위와 같은 방식으로 선언하면 안됨!
이는 [[0]*N]의 하나의 row를 N번 복제하는데 얕은 복사(shallow copy)를 수행하기 때문에,
그 row의 주소만 참조하게됨. 따라서 2차원배열의 모든 row는 동일한 리스트 객체를 참조하게됨
즉, 하나의 행을 수정하면 다른 행도 동일하게 수정되는 문제가 발생함.

2. 올바른 2차원 배열 선언 방법은
rows = cols = N 일때,
matrix = [[0 for i in range(cols)] for j in range(rows)]

혹은

matrix = [[0]*cols for _ in range(rows)]

이렇게 리스트 컴프리헨션을 사용해 선언하는 방법이다.

---

다시 풀어보기: 방향 인접행렬

#다시 풀어보기: 방향 인접행렬
import sys
sys.stdin = open("input.txt",'rt')
input = sys.stdin.readline

N,M = map(int, input().split())
matrix = [[0 for _ in range(N+1)] for _ in range(N+1)]

for _ in range(M):
    row, col, weight = map(int, input().split())
    matrix[row][col] = weight

for i in range(1,N+1):
    for j in range(1,N+1):
        print(matrix[i][j], end=' ')
    print()