[이것이코딩테스트다]5장_탐색 알고리즘 DFS/BFS(4)_그래프(파이썬으로 그래프 표현하기)

#책 페이지 

p.134

 

#DFS,BFS를 알기 전 알아두어야 할 자료구조

스택, 큐, 재귀함수 

 

#DFS란

DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS를 설명하기 전에 먼저 그래프의 기본 구조를 알아야 한다. 

 

#그래프의 기본 구조

1. 노드와 간선

 

 

그래프는 노드(Node)(=정점(Vertex))와 간선(Edge)로 표현된다.

그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 

또한 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다' 라고 표현한다. 

 

 

 

 

2. 인접 행렬과 인접 리스트 

프로그래밍에선 그래프를 크게 3가지 방식으로 표현할 수 있다. 코딩 테스트에서는 이 두 방식 모두 필요하니 두 개념에 대해 바르게 알고 있도록 하자.

-인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식이다.

-인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식이다. 

 

#인접 행렬과 인접리스트 그림으로 보기

그래프를 총 4가지의 경우로 나눠서 그림으로 표현해보자.

1. 가중치가 있는 그래프를 인접행렬로 표현

2. 가중치가 있는 그래프를 인접리스트로 표현

3. 가중치가 없는 그래프를 인접행렬로 표현

4. 가중치가 없는 그래프를 인접리스트로 표현

 

1,2가중치가 있는 그래프를 인접행렬, 인접리스트로

 

→가중치 있는 그래프를 인접행렬로 표현

연결 되어 있으면 - 가중치를 적고

연결이 안되어 있다면 - INF(무한대)

자기 자신이라면 - 0으로 적는다. 

 

→가중치 있는 그래프를 인접리스트로 표현

가중치와 쌍으로 적어준다. 

 

 

 

 

 

 

 

 

 

 

 

 

 

3,4가중치가 없는 그래프를 인접행렬과 인접리스트로 표현  

→가중치 없는 그래프를 인접행렬로 표현 

연결 되어 있으면 - T혹은 1

연결이 안되어 있다면 - F혹은 0

자기 자신이라면 - F혹은 0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#그래프를 코드로 나타내기

그래프를 총 4가지의 경우로 나눠서 코드로 표현해보자.

1. 가중치가 있는 그래프를 인접행렬로 표현

2. 가중치가 있는 그래프를 인접리스트로 표현

3. 가중치가 없는 그래프를 인접행렬로 표현

4. 가중치가 없는 그래프를 인접리스트로 표현

 

1. 가중치가 있는 그래프를 인접행렬로 표현

INF = 999999999 #무한의 비용 선언

#2차원 리스트를 이용해 인접 행렬 표현
graph=[
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)

#결과 [[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]

 

2. 가중치가 있는 그래프를 인접리스트로 표현

#행(ROW)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)] #[[],[],[]] 으로 만들어진다.

#노트 0에 연결된 노드 정보 저장(노드, 가중치)
graph[0].append((1,7))
graph[0].append((2,5))

#노드 1에 연결된 노드 정보 저장(노드, 가중치)
graph[1].append((0,7))

#노드 2에 연결된 노드 정보 저장(노드, 가중치)
graph[2].append((0,5))

print(graph)

#결과 [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

▲노드와 가중치 정보를 '쌍'으로 append한다. 튜플에 담아 append하면 된다. 

 

3. 가중치가 없는 그래프를 인접행렬로 표현

#2차원 리스트를 이용해 인접 행렬 표현
graph=[
    [False, True, True],
    [True, False, False],
    [True, False, False]
]

print(graph)

#결과 [[False, True, True], [True, False, False], [True, False, False]]

 

4. 가중치가 없는 그래프를 인접리스트로 표현

#행(ROW)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)] #[[],[],[]] 으로 만들어진다.

#노트 0에 연결된 노드 정보 저장(노드)
graph[0].append(1)
graph[0].append(2)

#노드 1에 연결된 노드 정보 저장(노드)
graph[1].append(0)

#노드 2에 연결된 노드 정보 저장(노드)
graph[2].append(0)

print(graph)

#결과 [[1, 2], [0], [0]]

 

#인접리스트와 인접행렬의 차이점

👉메모리 측면

인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을 수록 메모리가 불필요하게 낭비된다. 

반면 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.

 

👉속도 측면

인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. 인접 리스트 방식에서는 연결된 데이터를 하나씩 확인해야 하기 때문이다. 

 

ex) 노트 1과 7이 연결되어 있는 지 확인해보자.

인접 행렬 방식에서는 graph[1][7]만 확인하면 끝이다. 

반면에 인접 리스트 방식에서는 노드 1에 대한 인접 리스트를 앞에서부터 차례대로 확인해야 한다. 

 

❔그렇다면 어떤 방식을 선택해야하는 걸까?

특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우 → 인접 리스트 방식

└이유 : 인접 리스트 방식이 인접 행렬 방식보다 메모리 공간의 낭비가 적기 때문 

그게 아닌 경우 → 인접 행렬 방식