Part5.14_완전탐색_부분집합 구하기(DFS)_인접행렬(가중치 방향 그래프)

Eugenius1st·2022년 1월 27일
0

Python_algorithm

목록 보기
42/83

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

내가 생각한 코드

너무 간단해서 민망한데..
규칙이랄게 없다 ㅋㅋㅋ ;;

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

n, m= map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
res = [([0]*n)for _ in range(n)]
for x in a: # 1 2 3 4 5 6 7 8 9
    tmp1=x[0]
    tmp2=x[1]
    tmp3=x[2]
    res[tmp1-1][tmp2-1] = tmp3

for i in res:
    for j in i:
        print(j, end=" ")
    print()

선생님 코드

노드와 간선의 집합을 그래프라고 한다.
노드가 동그란 것이고, 선이 간선이라고 한다.
문제를 풀기 전에

먼저 무방향 그래프부터 알아보자


무방향 그래프란 어느 방향으로도 갈 수 있는 그래프 이고,
항상 행 번호에서 열 번호로 노드가 이동할 수 있다고 이해하면 좋다.
그림과 같이 1행 2열에 1이 체크되어있다면,
1번 노드는 2번노드로 갈 수 있다는 의미이다,
그렇다면, 무방향 그래프이므로 2번노드도 1번노드로 갈 수 있다.
그래서 아래와 같이 무방향 그래프를 이차원 배열로 그려보면, 대칭의 그림이 출력되는 것을 알 수 있다.

본격 문제 인접행렬

가중치 방향 그래프에서
1 2 7 이라는 의미는, 1번 노드에서 2번 노드로 가는데. 가중치 값이 7이다. 라는 의미이다.
방향그래프는 1에서 2번으로만 가는 '방향' 이다.

import sys
sys.stdin = open("input.txt", "rt")
n,m = map(int,input().split())#n은 노드, m은 간선
# 무방향 그래프
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()
   

오엥? 나랑 똑같네 ?? 차이가 있다면... map으로 한번에 변수를 받아서 2줄이나 줄이셨다는거 ㅎㅎ..

profile
최강 프론트엔드 개발자가 되고싶은 안유진 입니다

0개의 댓글