[python] 백준 알고리즘 32942번 : 그래프와 그래프 - 인접 행렬, 인접 리스트

https://www.acmicpc.net/problem/32942
 
 
 

개념 - 동주햄에게 배운 개념

인접 행렬, 인접 리스트 예시, 유향 그래프

# 인접 리스트를 이용한 그래프 탐색
found link(root) 1
    visit 1
        found link 2
            visit 2
                found link 3
                    visit 3
                        link not found
                link not found
        found link 3
            already visited 
        found link 4
            visit 4
                found link 3
                    already visited
                link not found
        link not found 
end

# 수행 시간 계산 - 정점의 제곱
visit : 4 # 노드의 개수만큼 visit함
found link : 5 + 1 # 링크의 개수만큼 found함
link not found : 4 # 노드 개수만큼 link not found
already visited : 2 #  

정점의 개수 : N = 4, 간선의 개수 : M = 5 

수행시간 : T = visit +  found link +link not found + already visited 
             = (visit + aleardy visited) + found link + link not found
             = 2 * found link + link not found
             = 2 * (M+1) + N
             => O(M+N)

# 인접 행렬을 이용한 그래프 탐색
visited 1: o
visited 2: o
visited 3: o
visited 4: x

found link(root) 1
    visit 1
        link not found 1
        found link 2
            visit 2
                link not found 1
                link not found 2
                found link 3
                    visit 3
                        link not found 1
                        link not found 2
                        link not found 3
                        link not found 4
                link not found 4
        found link 3
            already visited
        found link 4
            visit 4
                link not found 1
                link not found 2
                found link 3
                    already visited
                link not found 4
end

# 수행 시간 계산 - 정점의 제곱
found link : 6
link not found : 11
visit + already visited = found link 
found link + link not found = visit * n 

풀이

A, B, C = map(int,input().split())

# G[x] = [, , , ,]: x에 연결된 정점들
adj_lst = [[] for _ in range(11)]
adj_mat = [[0] * 11 for _ in range(11)]


for x in range(1,11): 
    for y in range(1,11):
        if A*x + B*y == C:
            adj_lst[x].append(y) # 인접 리스트를 만드는 방법
            adj_mat[x][y] = 1 # 인접 행렬을 만드는 방법
            
def print_adj_mat(adj_mat):         
    for i in range(1,11): # 인접 행렬로 출력하는 방식
        conn = [j for j in range(1,11) if adj_mat[i][j] == 1]
        if conn:
            print(*conn)
        else:
            print(0)

def print_adj_lst(adj_lst):
    for i in range(1,11):
        if adj_lst[i]:
            print(*adj_lst[i])
        else:
            print(0)