[Python-CodingTest] 6-14. 인접행렬 (가중치 방향그래프)

인접행렬

시작하기 전에…

무방향 그래프란?

두 노드(a,b)가 연결되어있을 때 a->b도 가능하고 b->a도 가능하다.

입력

5 5
1 2
1 3
2 4
3 4
4 5

무방향 그래프 구현

import sys
sys.stdin = open("./input/in14.txt", "rt")

n,m=map(int,input().split()) # n: 노드개수 m: 간선개수
g=[[0]*(n+1) for _ in range(n+1)] # 인접행렬 그래프 (2차원 리스트) # n번 인덱스까지 생성

# 간선 정보 읽기
for i in range(m):
    a,b=map(int,input().split())
    g[a][b]=1 # a->b 가능
    g[b][a]=1 # b->a 가능

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

출력

0 1 1 0 0 
1 0 0 1 0 
1 0 0 1 0 
0 1 1 0 1 
0 0 0 1 0 

방향 그래프란?

두 노드(a,b)가 연결되어있을 때 화살표 방향에 따라 a->b만 가능할수도, b->a만 가능할수도, 양방향이 가능할수도 있다.

문제 정리

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

입력

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. 인접행렬 그래프(=g[][])를 2차원 배열 형태로 생성한다. (이때, 인덱스 번호와 노드번호가 일치하도록 행과 열을 각각 n+1개 생성한다.)
2. for문 안에서 g[][]에 간선의 방향에 맞는 가중치를 대입힌다. (g[a][b]라면 a->b)
3. 출력 시에 g[][]의 0번 행과 열은 무의미함으로 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
sys.stdin = open("./input/in15.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 # a->b 간선의 가중치는 c

for i in range(1,n+1): # g의 0번 행과 열은 무의미함으로 1번부터 출력
    for j in range(1,n+1):
        print(g[i][j],end=' ')
    print()

정리

• 인접행렬 그래프(2차원 리스트)를 생성할 때, 인덱스 번호와 노드번호가 일치하도록 행과 열을 각각 n+1개 생성한다.
• 출력 시에는 g[][]의 0번 행과 열은 무의미함으로 1번부터 출력한다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기