TIL - 인접 리스트

문제

- 그래프를 인접 리스트로 표현합니다.
- 간선(edge)을 추가하고 출력합니다.
- 방향 그래프와 무방향 그래프를 구분합니다.

 

 

문제풀이

def create_graph(vertices, edges, directed=False):
    """
    그래프 생성 (인접 리스트)
    
    Args:
        vertices: 정점 개수
        edges: (출발, 도착) 간선 리스트
        directed: 방향 그래프 여부
    
    Returns:
        그래프 딕셔너리
    """
    # TODO: 빈 그래프 초기화
    graph = {}

    
    for j in range(vertices):                           # vertices 만큼 돌기
        graph.setdefault(j, [])                         # 빈 값 추가 (setdefault : 키 있는지 검색, 없으면 기본값 넣기)
        
        # 양방향 그래프일때 역방향도 추가 
        if directed == False:
            for i in range(len(edges)):                 # 간선 리스트 개수만큼 돌기
                dict_key = edges[i][1]                  # key
                                
                if dict_key == j:                        # vertices 현재값이랑 key 가 동일하면
                    graph[dict_key].append(edges[i][0])  # 배열 value 값으로 복사하기 
        
        # 단방향 그래프
        for i in range(len(edges)):                     # 간선 리스트 개수만큼 돌기
            dict_key = edges[i][0]                      # key
            
            if dict_key == j:                           # vertices 현재값이랑 key 가 동일하면
                graph[dict_key].append(edges[i][1])     # 배열 만들어서 넣었다가 setdefault 로 이미 value 는 배열이니 append 로 추가 
                        
                            
    
    return graph

 

 

이중 for 문을 돌면서 외부 반복문 : 요소만큼 돌고, 내부 반복문 : 간선 리스트 개수만큼 돌면서 이어주기 형태로 구현했다. 

 

 

아래는 더 간단하게 코드를 개선했다. 

 

def create_graph(vertices, edges, directed=False):
    """
    그래프 생성 (인접 리스트)
    
    Args:
        vertices: 정점 개수
        edges: (출발, 도착) 간선 리스트
        directed: 방향 그래프 여부
    
    Returns:
        그래프 딕셔너리
    """
    # TODO: 빈 그래프 초기화
    graph = {}
    graph = {i: [] for i in range(vertices)}
    
	for s,e in edges:
        # graph.setdefault(s, [])
        graph[s].append(e)
        if not directed :
            graph[e].append(s)
    
    return graph

 

 

 

어려웠던 점

1. 개념만 찾아보고 풀었는데, 배열로 어떤 식으로 저장할 지는 혼자 생각해봤다. 
   • 일단 여기까지 노트에 적고, 실제로 j 가 0일 때 값만 넣어서 실행해보고 범위를 확장했다. 

 

 

1. 딕셔너리 컴프리헨션 
   • { } : 결과를 딕셔너리로 만들기 위해 중괄호 사용
   • 키_표현식: 값_표현식 : 딕셔너리에 들어갈 key: value 형태 지정
   • if 조건문 : 생략 가능. 특정 조건을 만족하는 데이터만 필터링할 때 사용  
     • 일반 for 문과 논리적으로 동일하다. 하지만 컴프리헨션이 더 빠르다.
     • for 문은 매 반복마다 squares.append 라는 이름의 속성을 조회해야한다.
     • 컴프리헨션은 내부적으로 파이썬 바이트코드 레벨에서 LIST_APPEND 라는 전용 명령어를 사용한다. 이름 조회 과정이 없다. (객체 생성 오버헤드 X)

{키_표현식: 값_표현식 for 변수 in 반복가능객체 if 조건문}

 

• 오버헤드
  • 본래 하고 싶은 일 자체와는 상관없이, 그 일을 하기 위해 추가로 드는 비용