[인프런] 인접행렬

그래프

• 노드와 노드 사이를 연결하는 선: 간선
• 노드끼리의 집합: 그래프
• 간선에 방향이 있는 경우: 방향 그래프
• 간선에 번호가 붙어있는 경우: 가중치 그래프
• 간선에 번호와 방향이 있는 경우: 가중치 방향 그래프

무방향 그래프 그리기

그럼 그래프를 코드로 어떻게 옮길까?

바로 2차원 리스트이다.

처음에는 모두 0으로 초기화를 한다. 0으로 초기화 된 값은 상호간에 연결이 존재하지 않는다는 뜻이다. 그래프를 그려보기 전에 전제 조건은 행에서 열로 이동한다고 이해해야 한다는 것이다.

만약 1번 노드와 2번 노드가 연결되어 있다면, 2차원 리스트에서는 (1, 2) 값을 1로 값을 변경해준다. 이 말은 ‘1번 행에서 2번 행으로 이동한다’라는 뜻이다.

이를 코드로 표현하면 g[a][b] = 1 과 같이 표현할 수 있다.

가중치 방향 그래프 그리기

예를 들어 1, 2, 7이라는 입력이 주어졌다고 하자. 이 말은 1번 노드에서 2번 노드로 가는데 가중치는 7이라는 뜻이다. 이를 코드로 구현하면 g[1][2] = 7 로 값을 변경해주면 된다. 무방향 그래프에서는 무조건 1로 변경해주었다면 가중치 방향 그래프에서는 주어진 가중치 값으로 값을 변경해주면 된다.

문제

아래 그림과 같은 그래프 정보를 인접행렬로 표현하라

• 첫째줄에는 n개의 정점의 수와 m개의 간선의 수가 주어진다. 그 다음부터 m줄에 걸쳐 연결정보와 거리비용(가중치)이 주어진다.

Solution

n, m = map(int, input().split())
graph = [[0] * (n+1) for _ in range(n+1)]

for i in range(m):
    row, col, weight = map(int, input().split())
    graph[row][col] = weight

for i in range(1, n+1):
    for j in range(1, n+1):
        print(graph[i][j], end=" ")
    print()