그래프라는 것은 노드와 간선의 집합을 말한다.
간선 중에서도 방향이 설정되어 있으면 방향그래프! 간선에 값까지 설정되어 있다면 가중치 방향 그래프 !!
일단 그 전에 그래프의 가장 기본이 되는 무방향 그래프, 거기서 방향을 추가한 방향 그래프 이것을 먼저 인접 행렬로 표현해보고 그 이후에 가중치 방향 그래프를 풀어나가자 !
파이썬에서 그래프를 풀 때는 인접행렬, 즉 2차원 리스트를 사용한다. 시작은 기본적으로 모두 0으로 초기화 시켜놓고 (연결이 되어 있지 않다는 뜻) 시작.
- 인접 행렬은 항상 행에서 열로 이동한다고 생각하자!
무방향 그래프
무방향 그래프는 행→열 열→행 모두 1로 해주면 둘 다 연결되어 있다고 생각하게 해주면 된다.
즉 g[a][b] = 1, g[b][a] = 1 모두 체크하면 돼
n,m = map(int, input().split()) #n은 노드 번호, m은 간선의 개수
g = list([0] * (n+1) for _ in range(n+1)) #g는 그래프
# 0~n-1이 아니라 1~n으로 접근하는게 편해 !
for i in range(m):
a,b = map(int, input().split())
g[a][b] = 1
g[b][a] = 1
for i in range(1,n+1):
for j in range(1,n+1):
print(g[i][j], end = " ")
print()위 코드를 보면 행 별로 생각하면 편해 즉 각 행이 어느 노드로 접근할 수 있는지(연결되어 있는지)를 나타내는 값이 1이야
가중치 방향 그래프
위에서 무방향 그래프를 봤으니 방향 그래프라면 [a][b] = 1만 해주면 된다고 생각할 수 있다.
가중치 방향 그래프는 이제 해당 값이 1(연결만 표시)이 아니라 그 값에 가중치를 넣어주면 된다.
for i in range(m):
a,b,c = map(int, input().split()) #c는 가중치 값
g[a][b] = c
for i in range(1,n+1):
for j in range(1,n+1):
print(g[i][j], end = " ")
print()앞으로 가중치 방향 그래프 문제를 풀 때는 위와 같이 인접행렬을 활용할 것이다.
경로 탐색(그래프 DFS)
문제
방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는
1 2 3 4 5
1 2 5
1 3 4 2 5
1 3 4 5
1 4 2 5
1 4 5
총 6 가지입니다.
그래프에서 경로란 방문한 노느는 중복해서 방문하지 않습니다.
▣ 입력설명
첫째 줄에는 정점의 수 N(2<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연결정보가 주어진다.
▣ 출력설명
총 가지수를 출력한다.
▣ 입력예제 1
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5
▣ 출력예제 1
6
import sys
sys.stdin = open("input.text", "rt")
n, m = map(int, input().split())
g = [[0] * (n+1) for _ in range(n+1)]
for i in range(m):
a,b = map(int, input().split())
g[a][b] = 1
ch = [0] * (n+1) #중복 체크리스트
cnt = 0
path = []
def DFS(v):
global cnt
if v == n: #종착 지점. 종료조건
cnt += 1
for x in path:
print(x, end = " ")
print()
else:
for i in range(1,n+1): #1~n번 노드까지 있잖아. 개수만큼 가지 뻗어서 확인해야지
if g[v][i] == 1 and ch[i] == 0: #해당 i 인접노드가 연결되어 있고 방문 전이라면
ch[i] = 1
path.append(i)
DFS(i)
path.pop() #백할 때는 경로에서 지워줘야지
ch[i] = 0 #백 트랙킹 이후 방문 표시 없애야지
ch[1] = 1 #시작은 1번노드니까 1번 방문 표시 하고 들어가야지
path.append(1) #시작 지점 경로에 넣고..
DFS(1)
print(cnt)코멘트
해당 문제가 이제 방향 그래프에 DFS를 섞어서 푸는 문제이다.
방문을 하면 체크리스트를 통해 방문했다고 해줘야해 !
이처럼 경로 탐색 문제는 DFS(재귀)를 돌면서 연결된 노드가 있는지 확인하고 연결되어 있다면 다음으로(DFS(2))로 넘어간다. (1→2) 그리고 2번 노드 방문했다고 체크 표시해줌!
계속 넘어가면서 이제 똑같은 행동을 하는거야 (대신 넘어가기 전에 이미 해당 노드 방문했는지 체크 리스트 확인) !
- 이제 마지막 노드 n번 노드에 도착했다면 여기서부터 중요해! 백트랙킹 과정에서 체크리스트에서 방문 표시한 것을 빼줘야해 !
해당 코드처럼 현재 종착점 노드 n이 아니라면 모든 가짓수를 확인하면서 (for i in range(1,n+1)) 해당 그래프에서 현재 노드와 인접한 노드인지를 확인한 후 그 인접 노드가 또 방문하기 전이라면 방문하는 식 !
-
결국 그래프에서 현재 방문하는 노드를 이전에 방문했는지를 확인하는 것이 중요하다.
-
이런 식으로 이제 문제를 많이 풀 것이다.
