[sw 사관학교 정글] [WEEK03] WIL 03주차 개발일지

[BFS, DFS, 위상정렬]

 

그래프 탐색 기본

그래프 탐색은 그래프 안에 어떤 버텍스들이 있는지 알고 싶을 때 사용

여러 노드(node or vertex)들이 간선(edge)으로 연결된 추상 네트워크

 

V = {a,b,c,d} / E = {{a,c},{a,d},{a,b},{b,d},{c,d}}  - 양 방향 그래프 이므로 간선의 집합에서 역도 성립한다.

 

그래프는 방향이 있는 그래프(directed)와 방향이 없는 그래프(undirected)

 

방향이 있는 그래프는 간선에 방향이 지정되어 있지 않아, 서로 인접(adjacent)해 있으며, 이웃(neighbor)이라함

 

차수(degree)

한 노드에 이어져 있는 간선의 수

차수가 0인 노드는 고립(isolated)되었다고 부름

방향이 없는 그래프는 입력 차수(in-degree)와 출력 차수(out-degree)로 나눔

 

인접(adjection)

두 노드간 유일한 엣지를 가지면 인접하다고 표현

 

이진트리

트리는 node와 edge로 구성

노드는 자식을 가질 수 있음

1번 node = root

루트 노드의 깊이를 1로 하고 한 단계 내려가면 깊이가 1 증가

모든 노드가 최대 두 개의 자식을 갖는 트리

이진트리 깊이: h

최대노드: 2 ^(h-1)

노드의 구성: 자기 자신의 값인 item과 자식의 위치인 left와 right를 가진다

기본적으로 트리의 크기가 N일 때, 전체 간선의 개수 N -1 개

구현

파이썬에서 이진 트리는 클래스를 통해서 인스턴스화가 가능

 

순회

중위, 후위, 전위

---

DFS BFS 문제 구분

인접리스트

인접행렬

 

DFS

현재 나의 위치에서 연결된 브랜치를 모두 방문 후 다음 브랜치로 넘어가는 방법

경우의 수

• 한 노드에서 제일 마지막 자식까지 탐색하고 돌아오는 과정을 '백트리킹(Backtracking)'
• ⚠방문한 노드는 확실하게 확인해줘야한다. 그렇치 않으면 무한루프에 빠지게 된다.
• 모든 경우를 하나하나 다 탐색을 해야될 경우 이용(조합, 순열 과 같이 경우의 수를 하나하나 다 찾고자 할때)

우선탐색 개념을 가진 순열 조합 구현에 활용

• 검색 대상 그래프가 정말 크다면 DFS를 고려
• 예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제
• 미로를 탐색할 때 한 방향으로 갈 수 있을때 까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로 부터 다른 방향으로 다시 탐색

*최단거리 문제라도 가중치나 이동과정에서 여러제약 사항이 있는 경우, DFS로 구현하는 것이 좋다

 

BFS

너비우선탐색으로 현재 나의 위치에서 가장 가까운 노드를 먼저 방문

방문하면서 현재 위치는 pop 해주고 방문한 곳은 체크한 뒤 방문할 곳은 큐에 넣는 과정

• 탐색시간이 더 걸리긴 하지만, 가중치에 대한 변수를 지속해서 관리할 수 있어, 코드 구현시 더 편리하다
• 현재 나의 위치에서 가장 가까운 노드들을 모두 방문
• 방문하며 현재위치 pop 방문할 곳 append 방문한곳 check
• 미로 탐색과 같은 최단거리, 임의의 경로를 찾는 문제, 최소횟수, 가중치 없는 그래프 최단 경로, 최단 거리를 구하되 조건이 여러 개 존재하는 경우(방문한 지점도 다시 방문 가능)
• 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

ex) 우리나라에서 직통도로로 연결된 지역 중, 서울과 경기도 사이에 존재하는 경로를 찾고싶을 때

깊이 우선 탐색의 경우(DFS) - 전국의 모든 도로를 다 살펴봐야할 수도 있다.

너비 우선 탐색의 경우(BFS) - 서울과 인접한 도로먼저 탐색

 

상, 하, 좌, 우 패턴

dx = [-1, 1, 0 ,0]dy = [0, 0, -1, 1]

대각선 + 상, 하, 좌, 우 패턴

dx = [-1, -1, -1, 0, 0, 1, 1, 1]dy = [-1, 0, 1, -1, 1, -1, 0, 1]

대각선 패턴

dx = [-1, -1, 1, 1]dy = [-1, 1, -1, 1]

 

최단거리

다익스트라

• 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘
• 우선순위 큐(= 힙트리) 이용하여 구현
• 그래프의 방향 유무는 상관 없음, 단 가중치가 음수이면 알고리즘 사용 불가
• 가장 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 문제

프로세스

1.출발 노드와, 도착 노드를 설정

2.알고 있는 모든 거리 값을 부여

3.출발 노드부터 시작하여, 방문하지 않은 인접 노드를 방문, 거리를 계산한 다음, 현재 알고있는 거리보다 짧으면 해당 값으로 갱신한다. (플로이드)

4.현재 노드에 인접한 모든 미방문 노드까지의 거리를 계산했다면, 현재 노드는 방문한 것이므로, 미방문 집합에서 제거한다.

5.도착 노드가 미방문 노드 집합에서 벗어나면, 알고리즘을 종료한다.

 

플로이드 와샬

• 최단거리를 구하는 알고리즘
• 음의 가중치가 존재해도 실행

k : 경유지
for k in range(1, v+1):
    # i : 출발지    
    for i in range(1, v+1):
        # j : 목적지
        for j in range(1, v+1):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
            
'''
i 와 j 사이 k를 거쳐가는

for k
	for i
		for j
'''

그래프 문제, 간선문제 풀이 구분 정리

• dfs, bfs 그래프 문제 기본 템플릿( 문제마다 수정은 필요함)

DFS

1. N = int(input())
2. graph [] # 2개가 있음
   1. graph[list(map(int, input().strip())) for _ in range(N) ]
3. visited [False] * for _ in range(N)
   1. 초기 시작값을 넣어 주어야 할 경우 밖에서 처리 끝내기
4. dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
5. def dfs():
6. 좌표안에서 동작하도록 if 문 작성
   1. if 0 <= nx < N and 0 <= ny < M and graph[nx][ny]== 0:
7. nx = x + dx[i] ny = y + dy[i] DFS(nx, ny)

BFS

1. N = int(input())
2. graph [] # 2개가 있음
   1. graph[list(map(int, input().strip())) for _ in range(N) ]
3. visited [False] * for _ in range(N)
   1. 초기 시작값을 넣어 주어야 할 경우 밖에서 처리 끝내기
4. dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
5. def bfs():
6. 좌표안에서 동작하도록 if 문 작성
   1. if 0 <= nx < N and 0 <= ny < M and graph[nx][ny]== 0:
7. nx = x + dx[i] ny = y + dy[i] DFS(nx, ny)

*dfs 는 sys.setrecursionlimit(10 ** 6)

 

*인덱스 고려를 위해 visited와 graph 초기 생성시에는(정점 + 1) graph.append 시에는 m 간선

---

Union - find

교집합이 없는 서로소 집합(Disjoint Set)

union 연산과 find 연산 단 2개만을 지원하는 자료구조

Find(x) 노드 x 의 부모중 루트를 반환하는 연산

dsjoint set에서 임의의 두 노들이 같은 집합에 속해있는지 확인하는 방법은 Find()로 나오는 값이 같은지 보는것

Union연산은 작은 트리의 부모를 큰 트리의 rootfh 하는 작업

---

위상정렬

조건

1. 간선이 방향성을 가진 그래프
2. 그래프 내부에 순환(cycle)이 없어야 한다

ex) 대학교 선수과목 구조

위상 정렬 프로세스

1. 진입 차수가 0인 정점을 큐에 삽입한다.
2. 큐에서 원소를 꺼내 해당 원소에 연결된 간선을 제거한다.
3. 간선을 제거한 후 진입 차수가 0이 된 정점을 큐에 삽입한다.
4. 위 과정을 반복한다

 

* 위상정렬 내용은https://velog.io/@younge/Python-그래프-위상-정렬-알고리즘 를 참고했습니다.

 

---

sort () 활용

key 매개 변수를 가지는 sort() 함수

sort(key = lambda x : x[2]) → 2번째 인자들을 기준으로 오름차순 정렬