DFS, BFS 그래프 탐색 알고리즘 1

그래프 자료구조 간단 정리

그래프 구현 방법의 차이

그래프(Graph)는 정점(Vertax, Node)과 간선(Edge)으로 이루어진 그래프이며 정점 간 연결관계를 간선으로 나타낸다.

그래프는 연결 상태에 따라 양방향, 방향 가중치, 완전 그래프등으로 분류된다. 그렇다면 그래프를 구현하는 방법으로 어떤 것들이 있을까?

• 인접 행렬 (Adjacency Matrix) : 간선의 개수와 무관하게 V^2의 공간 복잡도를 가지며 O(1)로 위치의 값을 찾아낼 수 있는 행렬식 구조이다.
• 인접 리스트 (Adjacency List) : 해당 정점에 연결된 다른 정점들을 찾는 방식으로 공간 복잡도는 O(E+V) 지만 확인하는데 오래걸린다. 

그래프의 특징

• 사이클이 있거나 없을 수 있다. 
  • 만약 없는 경우, 트리 구조라고 한다.
  • 루트 노드의 개념이 없다.
• 그래프는 크게 방향 그래프와 무방향 그래프로 나눈다.
  • 방향 그래프에는 진입차수와 진출차수가 있는데 진입차수를 활용한 알고리즘으로 위상 정렬이 있다.
  • 2개 이상의 경로가 가능하다.
• 보통 완전 탐색이나 최단 경로를 구하는 문제에서 많이 쓰인다.

# 인접 행렬

INF = 99999

graph = [
	[1, 0, 5],
    [8, INF, 0],
    [5, INF, 0],
]

# 인접 리스트

graph = [[] for _ in range(n)]

graph[0].append(3) # 0번 노드에 3번 노드 연결

---

 

오늘은 그래프 자료구조를 이용한 탐색 알고리즘에 대해 알아볼 예정이다.

DFS

깊이우선탐색(DFS, Depth-First Search)은 해당 루트노드부터 시작해 다음 분기(Branch)전 까지 깊게 탐색하는 알고리즘이다.

특징

• 단순 검색 속도는 BFS에 비해 느리지만 구현하기 간단한 알고리즘이다.
• 재귀 호출이나 스택을 사용하여 구현한다.
• 모든 노드를 방문하고자할때 사용한다.
• 주로, 미로나 연결 문제등으로 활용된다.

동작방식

1. 시작 노드을 스택에 넣는다. 
2. 최상단의 노드를 `pop`하고 방문 표시를 한다.
3. `pop`된 노드 중 방문을 하지 않은 인접 노드가 있다면 스택에 `push` 한다. (인접노드가 여러개라면 낮은 인덱스 부터)

재귀 함수를 이용하면 훨씬 간단하게 구현할 수 있다. 

현재 노드에 방문처리를 하고 인접 노드 중 방문하지 않는 인접 노드를 다시 재귀 호출하면 된다.

 

DFS는 깊이가 점점 깊어지기 때문에 RecursionError가 발생할 수 있다. 

이러한 경우는 `sys.setrecursionlimit(N)`을 이용해 재귀에 제한을 둘 수 있다. 

DFS

재귀 함수를 사용하는 경우와 스택을 사용하는 경우 탐색 과정에 차이가 있다.

• 재귀 함수를 이용한 DFS는 사전식 순서이다.
• 스택을 활용한 DFS는 역순으로 방문하는 순서이다.

BFS

너비우선탐색(BFS, Breadth-First Search)은 한 정점으로부터 연결되어있는 모든 정점을 먼저 탐색하는 알고리즘이다. 

특징

• DFS보다 빠르게 동작하지만 탐색할 정점들을 저장해야하므로 공간이 많이 필요하다.
• 일반적으로 큐 자료구조를 사용해 구현한다. 보통 파이썬에선 `deque`를 사용하곤 한다.
• 두 노드 사이의 최단 경로나 임의의 경로를 찾을 때 사용한다. 
• 주로, 주변위치나 가장 먼 노드 찾기 등으로 활용된다.

동작방식

1. 시작 노드을 큐에 넣는다.
2. 큐에 가장 앞단에 있는 노드를 `popleft`하고 방문 표시를 한다.
3.  추출한 노드의 인접 노드 중 방문하지 않은 인접 노드를 다시 큐에 `push`한다.

BFS

 

어떤 노드를 방문했는지 알기 위해 `visited`라는 방문 여부 검사가 필요하다.  그래야만 무한 루프에 빠지지 않는다.

 

---

탐색하면서 알아두어야할 N가지!

방향 벡터

DFS나 BFS 문제를 풀다보면 방향에 맞게 이동을 하는 시뮬레이션 문제가 출제되는 경우가 많다.

이럴 때, 방향 벡터를 사용하게 된다. 상하좌우, 대각선 등을 벡터화하여 사용하는데 일반적으로 동서남북 방향으로 이동하는 문제가 자주 출제된다. 초기 방향을 설정하기 위해 `delta x, y`를 상하좌우로 설정한다. 

# 북 동 남 서
dx = [ -1, 0, 1, 0]
dy = [ 0, 1, 0, -1]

nx = x + dx[i] # 다음 방향
ny = y + dy[i]

# 2차원 배열에 벗어나거나 조건에 부합하는 값일 경우 등으로 조건 체크를 한다.
if 0 <= nx < N and 0 <= ny < M and not array[nx][ny]:
	array[nx][ny] = True

 

Flood Fill (플러드필)

플러드 필은 각각의 영역을 다른색으로 채우는(Fill) 알고리즘이다. 

다차원 배열에서 연결된 영역(그룹)을 찾는 알고리즘이다.

 

예시로 다음 유기농 배추(백준) 문제를 풀어보자. 

다음과 같은 맵이 주어진다고 했을 때, 가로 길이(M)와 세로 길이(N)가 주어진다. 

여기서 배추가 심어져 있는 위치(K)는 1로 표시하고 그렇지 않는 곳은 0으로 표시한다. 

배추가 상하좌우로 다른 배추가 위치해 있으면 서로 인접한 곳이고 이런 경우에 배추흰지렁이가 있다고 한다.

그럼 배추흰지렁이의 갯수를 구하는 문제이다. 배추흰지렁이의 개수는 배추들이 연결된 그룹과 동일하다. 

 

먼저 위 그림처럼 2차원 배열에 배추가 있는 위치와 배추가 없는 위치를 입력 받는다.

그런 다음, 실제로 좌상단 부터 우하단까지 배추가 있는지 아니면 방문한 적이 있는지 확인할 예정이다.

만약 방문한 적이 있다면 넘어간다. 방문 여부를 위해 0,1 혹은 불린으로 된 새로운 이차원 배열을 생성한다. 

• 해당 위치가 배추인 경우
• 방문 한 적이 없는 경우

위에 해당 하는 경우에만 DFS 탐색을 해 연결된 그룹을 찾아내고 그렇지 않은 경우에는 `continue`로 넘어간다. 

 

만약, 위 조건에 해당하면 DFS로 넘어가게 되는데 우선, 방문여부을 한적 있으면 `return`으로 해당 함수를 종료하지만 지금은 방문 한 적이 없기 때문에 방향 벡터를 이용해 방문 여부와 배추 여부를 체크해나간다. 

 

이렇게 되면 배추흰지렁이의 개수를 찾아낼 수 있다! 비슷한 문제 유형으로 단지번호 붙이기도 풀어보자.

 

Flood Fill 이해하기 쉬운 Youtube 영상↗

 

사이클 여부를 확인하기

보통 사이클의 여부를 확인하는 문제라면 방문은 이미 했지만 처리가 되지 않았을 때의 노드를 찾으면 된다. 

그렇다면 먼저 방문 여부와 처리 여부에 대한 리스트를 만들어 첫번째 노드 부터 사이클(`is_cycle`)이 도는지 확인하면 된다.

 

예를 들어, 텀 프로젝트(백준) 문제이다. 

문제는 프로젝트 팀을 구성하기 위해 모든 학생들이 함께하고 싶은 학생을 선택할 수 있다. 

• 학생들이(S1~ Sr) S1이 S1을 선택하는 경우나 S1→S2→S3→S1 이런식으로 선택하는 경우는 팀이 될 수 있다.
  • 즉, 혼자서도 팀을 할 수 있다는 뜻이다.

그렇다면 다음 그림의 학생이 있다고 가정한다면, (예, 1번은 3번 학생과 같이 하고 싶다.) 프로젝트 팀에도 속하지 않는 학생의 수를 계산하자.

 

먼저, 한번씩 방문한 적 없던 학생 위주로 순서대로 사이클 여부를 확인해본다.

첫번째 노드(`x`) 부터 방문 처리를 하고 다음 노드(`y`)를 이전에 방문한 적이 있는지 없는지 확인한다.

def is_cycle(x):
	# 1. 우선 방문 처리
	visited[x] = True
    # 2. 다음 노드 확인
    y = array[x]

 

그다음 그 다음 노드가 방문여부에 따라 사이클 발생여부가 달라지게 된다.

• 방문한 적이 없었던 노드이다.
• 방문한 적이 있었던 노드이다. 그러나 아직 처리하지 못했다. (사이클이 발생한 경우이다.)

만약 방문한 적이 없었던 노드라면 `is_cycle`을 통해 다시 다음 노드를 찾아간다.

그러나 만약에 자기 자신의 노드(혼자 팀 프로젝트하는 학생)라면 result 값에 값을 넣고 처리를 완료한다.

 

다시 `x`(1)로 돌아와 처리를 해주면 된다.

 

    if not visited[y]:
        # 방문 한 적이 없는 경우
        is_cycle(y)
    elif not finished[y]:
        # 방문 한 적은 있으나 완료하지 못한 경우 -> 사이클이 발생한 경우다.
        while y != x:
            result.append(y)
            y = array[y]
        result.append(x)
    # 현재 노드의 처리 완료
    finished[x] = True

 

그렇다면 이번엔 다른 경우다.

4번 학생이 7번 학생과 팀 과제를 하고 싶다고 했을 때, 위 방법과 동일하게 진행한다.

 

 

6번 학생이 4번 학생과 팀프로젝트를 하고 싶다 했을 때 4번 학생은 한번 방문한 적 있는 노드이다.

그러므로, 사이클이 발생한다는 것을 알 수 있다. 이때, x와 y가 다르기 때문에 다음 반복문을 진행한다.

    elif not finished[y]:
        # 방문 한 적은 있으나 완료하지 못한 경우 -> 사이클이 발생한 경우다.
        while y != x:
            result.append(y)
            y = array[y]
        result.append(x)

 

 

이번에도 x와 y가 값이 다르다. 그러므로 다시 `while` 반복문을 진행해 사이클이 다시 되돌아올 때까지 반복한다.

 

결국엔 사이클에 있는 값들을 다 넣고 사이클 함수를 종료하면 

전체 값에서 사이클에 있는 값을 빼면 속하지 않는 학생 수를 구할 수 있다.

print(n - len(result))

 

만약 방향이 없는 경우에는 문제를 어떻게 풀까?

무방향 그래프인 경우 현재 노드의 인접한 노드 중 직전 노드인 경우를 제외 하면 된다. 

for i in graph[node]:
	if visited[i]:
    	if i != prev: # i가 직전노드(prev)가 아닌 경우 
        	return True # 사이클 발생
    else:
    	if is_cycle(i, node):
        	return True
return False

---

풀어보기 좋은 문제들

• DFS와 BFS - 백준
• 단어 변환 - 프로그래머스
• 여행 경로 - 프로그래머스
• 가장 먼 노드 - 프로그래머스
• 특정 거리의 도시 찾기 - 백준
• 연구소 - 백준
• 경쟁적 전염 - 백준