[알고리즘/코드트리] dfs, bfs

그래프 상에서의 DFS 탐색

어떤 문제를 풀 때 보통은 대상과 대상 사이의 관련이 있는 경우가 많다. 예를 들어 사람과 사람 사이의 관계를 표현해야하거나 물건 살 때 물건과 물건 간의 상관관계를 따져야할 일이 많다. 이런 작업을 할 때는 데이터 간의 관계를 표현하는 게 필요해진다. 그런 상황에서 그래프가 유용하게 사용된다.
그래프는 정점과 간선으로 구성되어있다.
정점은 사람, 물건과 같은 것이고 상관관계는 간선으로 표시한다.

코딩테스트에서는 데이터의 상태를 숫자로 나타내는 경우가 많은데 그럴 때는 노드(정점)에 숫자로 표시하면 된다. 1번 데이터, 2번 데이터.. 이런 식으로 데이터에 네이밍이 되어있다면 1번 노드, 2번 노드.. 로 표현 가능핟. 그리고 데이터 2개 간의 상관 관계를 나타낼 때 A 가 B 로는 길이 있고 B 에서 A 로는 길이 없는 일방 통행을 표시한다고 하면 그냥 A-B 로 간선을 나타내기엔 역부족이다. 이때는 방향을 표시해줄 수 있고, 방향이 표시된 그래프가 방향그래프이다.

그래프는 간선에 가중치를 둘 수 있는데 예를 들어 A가 B를 좋아하고 C도 B 를 좋아할 때 똑같은 마음으로 좋아하진 않을 것이다. A 는 B를 5만큼 좋아하고 C는 B 를 10만큼 좋아한다면 이러한 정보를 간선에 가중치로 표현할 수 있다. A----5---> B <-----10-----C
이런 예시에서 인기 지수는 어떻게 알 수 있을까? 이때 알아야하는 개념이 진입 차수, 진출 차수인데 B 를 기준으로 생각했을때 들어오는 화살표는 2개 나가는 화살표는 0개이다. 인기지수는 당연히 들어오는 화살표로 (진입차수) 알 수 있을 것이다.

모두가 연결된 그래프를 연결 그래프이고, 연결되지 않은 부분이 있으면 비연결 그래프라고 한다.

그래프 구현 방법

그래프는 보통은 인접 행렬과 인접 리스트로 구현한다.

인접 행렬
인접 행렬로 구현할 때는 행에 노드들을 넣고 열에도 노드들을 넣으면 2차원 배열이 생성될 것이다. 아마 원소의 개수는 노드수의 제곱이 된다. 만약 1번 노드에서 2번 노드로 가는 관계를 인접행렬로 표현한다면 1행2열의 값을 1로 표시해주면 되고, 3번 노드에서 5번 노드로 가는 관계를 인접 행렬로 표현한다면 3행5열은 1로 표시해줄 수 있을 것이다. 그리고 관계가 없는 값들은 0으로 표시해주면 된다.
물론 이 경우는 가중치가 없는 경우에 대한 설명이고, 만약 가중치가 있다면 1이 아니라 가중치로 표현해줄 수 있다.

이를 구현하려면 입력 들어오는 것에 따라 해주면 된다. 1 2 이 입력이 들어온다면 리스트에 대해 arr[1][2] = 1 이런 식으로 입력을 받을 때마다 넣어주면 된다.

인접 리스트
인접 리스트로 그래프를 만드는 방법도 있다.
인접 리스트는 행렬이 아니고 각 노드에서 연결되어있는 애들만 리스트로 관리하는 것이다.
1번 노드에서 2번,3번과 연결되어 있다면 1번 노드 리스트안에 2,3 을 넣어주고,
2번 노드에서 아무것도 연결되어 있지 않다면 2번 노드 리스트 안에 아무것도 넣어주지 않고,
3번 노드에서 2,5 번과 연결되어 있다면 3번 노드 리스트 안에 2,5 를 넣어주고,
4번 노드에서 3,6번과 연결되어 있다면 4번 노드 리스트 안에 3,6을 넣어주고
5번 노드에서 4번과 연결되어 있다면 5번 노드 리스트 안에 5를 넣어준다.
이런 식으로 각 노드들에 대해 리스트를 만들고 각 리스트 안에는 연결되어 있는 노드들을 넣어주면 된다.

파이썬을 기준으로 인접 리스트를 구현하려면 v[a].push_back() 을 통해 a 번째 리스트에 push_back으로 원소를 넣어주면 된다.

인접리스트와 인접 행렬의 차이
인접 리스트와 인접 행렬은 시간복잡도와 공간복잡도가 다르기 때문에 상황에 맞는 걸 쓰면 된다.
인접 행렬은 N^2 의 공간을 썼는데 인접 리스트는 간선의 수만큼 공간을 쓰기 때문에 공간적 이점이 있을 수 있다. 만약 탐색을 해야하는 경우에 인접 리스트는 딱 연결되어 있는 만큼만 탐색을 해도 되는데 인접 행렬에서는 모든 배열을 탐색해야한다. 만약 3노드와 2노드가 연결되어있는지 확인할 때 인접 행렬을 쓰면 arr[3][2] 과 arr[2][3] 만 확인하고 오면 되는데 인접 리스트를 사용할 때는 3번 노드의 리스트를 순회하고 2번 노드의 리스트도 순회해야하므로 번거로울 수 있다.
케이스를 잘 고려해서 짜야하는데 대부분은 인접 리스트로 짜도 문제가 없이 나온다.

DFS

DFS 와 BFS 가 코딩테스트에서 가장 많이 나오는 유형 중 하나이다.
완전 탐색, DFS, BFS, DP 가 가장 많이 나오는 유형이다.
이전 시간에 백트래킹을 배웠는데 백트래킹을 DFS 이전에 배운 이유는 DFS 에서 백트래킹이 사용되기 때문이다.

DFS 는 그래프를 어떤 식으로 탐색할 건지 중에 하나이다. D 는 Depth(깊이) 를 의미한다. 어떤 정점에서 시작해서 탐색을 하는데 문제에서 보통은 어떤 우선순위로 탐색하라고 준다. DFS 는 탐색하는 노드에서 우선순위가 가장 높은애로 탐색하며 들어간다. 깊이가 깊어진다는 표현을 쓴 이유는 계속해서 우선순위가 높은애를 탐색하기 떄문에 계속 파고 드는 방식이기 때문이다 .

1. 그래프 탐색

https://www.codetree.ai/missions/2/problems/graph-traversal?&utm_source=clipboard&utm_medium=text

입력 형식
첫 번째 줄에는 N과 M이 공백을 사이에 두고 주어지고,
두 번째 줄부터는 M개의 줄에 걸쳐 (x,y)가 공백을 사이에 두고 주어집니다.

(x,y)는 두 정점 x,y 가 연결되어 있음을 의미합니다. (x,y) 쌍이 동일한 연결관계가 두 번 이상 주어지는 경우는 없다고 가정해도 좋습니다. (1≤x,y≤N)

1≤N≤1,000
0≤M≤min(10,000, 2N(N−1))

출력 형식
1번 정점에서 시작하여 주어진 간선을 따라 이동했을 때 도달 할 수 있는 서로 다른 정점의 수를 출력해주세요. 단, 1번 정점을 제외한 정점의 수를 구해주세요.

입력:
5 4
1 2
1 3
2 3
4 5

출력:
2

내가 짠 코드

n, m = tuple(map(int, input().split()))

g = [[] for _ in range(n+1)]

for i in range(m):
    x, y = tuple(map(int, input().split()))
    g[x].append(y)
    g[y].append(x)


visited = [0 for _ in range(n+1)]

def dfs(node):
    if visited[node]:
        return
    visited[node] = 1 
    for next_node in g[node]:
        dfs(next_node)

dfs(1)
cnt = 0
for i in visited:
    if i==1:
        cnt += 1
print(cnt-1)

2. 두 방향 탈출 가능 여부 판별하기

https://www.codetree.ai/missions/2/problems/determine-escapableness-with-2-ways?&utm_source=clipboard&utm_medium=text

입력 형식
첫 번째 줄에는 n과 m이 공백을 사이에 두고 주어지고,
두 번째 줄부터 (n+1)번째 줄까지는 각 행에 뱀이 없는 경우 1, 뱀이 있는 경우 0이 입력으로 공백을 사이에 두고 주어집니다. 시작 칸과 끝 칸에는 뱀이 주어지지 않는다고 가정해도 좋습니다.

2 ≤ n, m ≤ 100

출력 형식
좌측 상단에서 출발하여 우측 하단까지 뱀에게 물리지 않고 탈출 가능한 경로가 있으면 1, 없으면 0을 출력합니다.

입출력 예제
예제1
입력:
5 5
1 0 1 1 1
1 0 1 0 1
1 0 1 1 1
1 0 1 0 1
1 1 1 0 1

출력:
0

내가 짠 코드

n,m = tuple(map(int, input().split()))

arr = [list(map(int, input().split())) for _ in range(n)]

visited = [[0]*m for _ in range(n)]
drs, dcs = [1,0], [0, 1]


def in_range(r,c):
    return 0<=r<n and 0<=c<m

def dfs(r, c):
    if visited[r][c]==1:
        return
    visited[r][c] = 1
    for i in range(2):
        new_r, new_c = r + drs[i], c + dcs[i]
        if in_range(new_r,new_c) and arr[new_r][new_c] == 1:
            dfs(new_r, new_c)

dfs(0,0)

if visited[n-1][m-1]==1:
    print(1)
else:
    print(0)

BFS 탐색

BFS 는 그래프 너비 우선 탐색이고, 깊이가 얕은 애들을 먼저 탐색한다는 개념이다 루트 노드가 0이고 간선 하나로 연결된게 깊이 1 이고 간선 두 개를 타야하는게 깊이 2 인데, 깊이 1인 것들 먼저 탐색하고 깊이 2인것들 탐색하고 이렇게 깊이가 깊어지게 된다.
BFS 를 사용하려면 큐를 사용한다.

큐를 사용하면 깊이 순으로 탐색할 수 있다.
큐는 실생활에서 많이 볼 수 있는 구조로 줄 설 때 웨이팅하는 것과 같다. 선입선출 구조로 FIFO 구조라고 한다. 큐를 사용하면 먼저 큐에 들어온 녀석이 먼저 나가게 되는데 출발지점으로 부터 깊이가 얕은 애들을 큐에 넣어두고 하나씩 탐색하면서 그녀석들의 연결된 녀석들을 또 다시 넣는다면 가장 먼저 들어간 애들은 깊이가 낮은 애들이 된다.

1. 네 방향 탈출 가능 여부 판별하기

https://www.codetree.ai/missions/2/problems/determine-escapableness-with-4-ways?&utm_source=clipboard&utm_medium=text

입력 형식
첫번째 줄에는 n과 m이 공백을 사이에 두고 주어지고,
두번째 줄부터 (n+1)번째 줄까지는 각 행에 뱀이 없는 경우 1, 뱀이 있는 경우 0이 입력으로 공백을 사이에 두고 주어집니다. 시작 칸과 끝 칸에는 뱀이 주어지지 않는다고 가정해도 좋습니다.
2 ≤ n, m ≤ 100

출력 형식
좌측 상단에서 출발하여 우측 하단까지 뱀에게 물리지 않고 탈출 가능한 경로가 있으면 1, 없으면 0을 출력합니다.

입출력 예제
예제1
입력:
5 5
1 0 1 1 1
1 0 1 0 1
1 0 1 1 1
1 0 1 0 1
1 1 1 0 1

출력:
1

내가 짠 코드

from collections import deque

# n: 행의 수, m: 열의 수 입력 받기
n, m = tuple(map(int, input().split()))

# 2차원 배열을 입력 받아 arr에 저장
arr = [list(map(int, input().split())) for _ in range(n)]

# 이동 방향을 나타내는 리스트 (하, 상, 우, 좌)
drs, dcs = [1,-1,0,0], [0,0,1,-1]

# BFS를 위한 큐 생성
queue = deque()

# 방문 여부를 기록하는 배열
visited = [[0]*m for _ in range(n)]

# 주어진 좌표 (r, c)가 범위 내에 있는지 확인하는 함수
def in_range(r, c):
    return 0<=r<n and 0<=c<m

# BFS 탐색 함수
def bfs():
    while queue:
        r, c = queue.popleft()  # 큐에서 현재 위치를 꺼냄
        for dr, dc in zip(drs, dcs):  # 4방향으로 이동
            new_r, new_c = r + dr, c + dc

            # 새로운 위치가 범위 내에 있고, 1이며, 방문하지 않았으면
            if in_range(new_r, new_c) and arr[new_r][new_c] == 1 and not visited[new_r][new_c]:
                visited[new_r][new_c] = 1  # 방문 기록
                queue.append((new_r, new_c))  # 큐에 추가

# 시작점 (0, 0)에서 BFS 시작
queue.append((0, 0))
visited[0][0] = 1

bfs()

# 도착점 (n-1, m-1)에 도달했는지 확인
if visited[n-1][m-1] == 1:
    print(1)
else:
    print(0)

2. 최소 경로로 탈출 하기

https://www.codetree.ai/missions/2/problems/escape-with-min-distance?&utm_source=clipboard&utm_medium=text

입력 형식
첫 번째 줄에는 n과 m이 공백을 사이에 두고 주어지고,
두 번째 줄부터 (n+1)번째 줄까지는 각 행에 뱀이 없는 경우 1, 뱀이 있는 경우 0이 입력으로 공백을 사이에 두고 주어집니다. 시작과 끝 지점에는 뱀이 주어지지 않는다고 가정해도 좋습니다.
2 ≤ n, m ≤ 100

출력 형식
좌측 상단에서 출발하여 우측 하단까지 이동 가능한 경로 중 최단 거리를 출력합니다. 불가능한 경우 -1을 출력합니다.

입출력 예제
예제1
입력:
5 5
1 0 1 1 1
1 0 1 0 1
1 0 1 1 1
1 0 1 0 1
1 1 1 0 1
출력:
12

내가 짠 코드
다음의 문제는 STEP 배열이 따로 필요하게 된다. bfs 로 진행하면 가중치가 전부 동일하다면 BFS 방식을 쓰면 최단거리를 구할 수 있어서 굉장히 유용하다.

from collections import deque

n ,m = tuple(map(int, input().split()))

arr = [list(map(int, input().split())) for _ in range(n)]

drs, dcs = [0,0,-1,1],[1,-1,0,0]

def in_range(r,c):
    return 0<=r<n and 0<=c<m

# 깊이를 담기 위한 배열
step = [
    [0 for _ in range(m)]
    for _ in range(n)
]

# 방문 여부를 위한 배열
visited = [
    [0 for _ in range(m)]
    for _ in range(n)
]

q = deque()

def push(r, c, s):
    step[r][c] = s
    visited[r][c]= 1
    q.append((r,c))

def bfs():
    while q:
        r, c = q.popleft()
        for dr, dc in zip(drs, dcs):
            new_r, new_c = r + dr, c+ dc
            if in_range(new_r, new_c) and visited[new_r][new_c]== 0 and arr[new_r][new_c]==1:
                push(new_r, new_c, step[r][c] + 1)
            
push(0, 0, 0)
bfs()

if visited[n-1][m-1] == 1:
    print(step[n-1][m-1])
else:
    print(-1)