[알고리즘] BFS DFS

BFS DFS

간단 정리

 

DFS

스택으로 구현

스택에 추가되는 경우: 현재 노드에서 방문하지 않은 노드 중에 다음 방문예정인 노드

스택에서 빠지는 경우: 주변 노드들이 다 방문된 경우

 

한 노드에서 깊이 탐색이 종료된 시점에 저장해야할 값이 있다면,

인접 노드에서 재귀를 마치고 올라올 때 반환하는 값을 사용하면 된다.

재귀를 마치고 올라온다는 뜻은 주변 노드들이 다 방문된 경우이므로 스택에서 빠질 때, 즉 함수가 끝나는 시점에서 반환한다. 

 

BFS

큐로 구현

큐에 추가되는 경우: 현재 노드에서 방문하지 않은 노드 전부

큐에서 빠지는 경우: 방문하면서 빠진다

 

큐를 이용하기 때문에, 시작 노드로부터 떨어진 거리가 오름차순으로 정렬됨을 보장한다.

따라서 시작 노드로부터 조건을 만족하는 최소 거리 노드를 구할 수 있다.

 

---

 

예제

 

토마토

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

from collections import deque
import sys


input = lambda: sys.stdin.readline().rstrip()
M, N = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

last_day = 0
visited = [[False]*M for _ in range(N)]
q = deque()

# 초기 익은 토마토 큐에 넣기
# 그리고 모든 토마토 개수 알아내기
total_tomato = 0
for i in range(N):
    for j in range(M):
        if graph[i][j] != -1:
            total_tomato += 1
            if graph[i][j] == 1:
                q.append((i, j, 0))

di = [0, 0, 1, -1]
dj = [1, -1, 0, 0]
while q:
    i, j, cur_day = q.popleft()
    if visited[i][j]:
        continue

    visited[i][j] = True
    graph[i][j] = 1
    last_day = max(last_day, cur_day)
    total_tomato -= 1
    for d in range(4):
        ni, nj = i+di[d], j+dj[d]
        if 0 <= ni < N and 0 <= nj < M and not visited[ni][nj] and graph[ni][nj] == 0:
            q.append((ni, nj, cur_day+1))

print(last_day if total_tomato == 0 else -1)

 

익은 토마토가 익지 않은 토마토에 영향을 준다. 4방향으로 하루 씩 익어갈 때, 필요한 일수.

bfs 전형적인 문제라고 할 수 있다.

이 문제에서 주의해야할 점은 모든 토마토가 익지 않을 때 예외 출력, 처음에 익은 토마토가 여러 개라서 초기 대입과정이 있다는 것이다.

 

 

---

 

 

숨바꼭질3

 

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

from collections import deque


N, K = map(int, input().split())

n = 200_000
answer = n
visited = [False] * n
q = deque([(N, 0)])
while q:
    p, time = q.popleft()

    if visited[p]:
        continue

    visited[p] = True
    if p == K:
        answer = min(answer, time)

    # 2배 위치로
    np = p*2
    while np < n and not visited[np]:
        q.append((np, time))
        np *= 2

    np_1, np_2 = p-1, p+1
    if 0 <= np_1 < n and not visited[np_1]:
        q.append((np_1, time+1))
    if 0 <= np_2 < n and not visited[np_2]:
        q.append((np_2, time+1))

print(answer)

최소 시간을 알기 위해서 bfs 를 사용했다.

탐색에 필요한 visited 크기를 최적화할 수 없을 거 같아, 안전한 크기로 선언했다.

방문 처리를 명확히 할 것

 

import sys

read = sys.stdin.readline

n, k = map(int, read().split())


def solution(n, k):
	if n >= k:
		return n - k
	elif k == 1:
		return 1
	elif k % 2:
		return 1 + min(solution(n, k - 1), solution(n, k + 1))
	else:
		return min(solution(n, k // 2), k - n)


result = solution(n, k)
print(result)

공개된 풀이 중에 가독성이 좋은 코드를 가져왔다.

top-down dp를 사용하여 풀이했다.

문제의 조건을 보다 잘 이해했고 논리가 깔끔해서 인상적이다.

 

 

---

 

 

공주님을 구해라!

https://www.acmicpc.net/problem/17836

17836번: 공주님을 구해라!

 

from collections import deque
import sys


input = lambda: sys.stdin.readline().rstrip()
N, M, T = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

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

answer = "Fail"
visited = [[False]*M for _ in range(N)]
visited_with_gram = [[False]*M for _ in range(N)]
q = deque([(0, 0, 0, False)])
while q:
    x, y, t, with_gram = q.popleft()

    # 시간이 초과한 경우
    if t > T:
        answer = "Fail"
        break

    # 공주를 구함
    if (x, y) == (N-1, M-1):
        answer = t
        break

    # 이미 방문한 경우
    if with_gram:
        if visited_with_gram[x][y]:
            continue
    elif visited[x][y]:
        continue

    # 그람을 획득
    if graph[x][y] == 2:
        with_gram = True

    visited[x][y] = True
    if with_gram:
        visited_with_gram[x][y] = True

    for d in range(4):
        nx, ny = x + dx[d], y+dy[d]
        if 0 <= nx < N and 0 <= ny < M:
            if with_gram and not visited_with_gram[nx][ny]:
                q.append((nx, ny, t+1, with_gram))

            elif not visited[nx][ny] and graph[nx][ny] != 1:
                q.append((nx, ny, t+1, with_gram))

print(answer)

 

answer의 기본값을 None으로 설정해서 고생했다.

시간을 초과하는 것 말고도 공주를 구할 수 없는 경우를 놓쳤다.

모든 타일을 거치고도 조건을 만족시키지 못 했을 때, break 문이 아니라도 반복문이 끝날 수 있음을 알았다.

 

 

---

 

 

숫자고르기

https://www.acmicpc.net/problem/2668

2668번: 숫자고르기

 

import sys


def dfs(curr):
    global answer

    a, b = arr[curr]
    s_1.add(a)
    s_2.add(b)
    if s_1 == s_2:
        answer |= s_1

    elif len(s_1) == len(s_2):
        dfs(b)


input = lambda: sys.stdin.readline().rstrip()
N = int(input())
arr = [[i, 0] for i in range(N+1)]
for i in range(1, N+1):
    arr[i][1] = int(input())

answer = set()
for i in range(1, N+1):
    s_1, s_2 = set(), set()
    dfs(i)

print(len(answer))
print(*sorted(answer), sep="\n")

 

문제의 조건을 만족하는 집합의 부분집합은 조건을 만족할 수 없음을 이해한다.

주의해야할 점은 답을 출력하기 위한 리스트의 원소가 중복될 수 있다. (같은 graph를 다른 순서로 순회하는 경우)

한편, 꼬리는 무는 문제이기 때문에 dfs를 사용했다.

 

이 문제로 새롭게 알게된 내용이

파이썬 reference value는 모두 global을 안 붙여도 되는 줄 알았는데,

instance method로 접근하는 경우가 아니면(즉, 위 수식에서  answer |= s_1 처럼 대입) global로 변수를 가져와야 한다.

 

 

---

 

 

알파벳

https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

import sys


dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]


def alpha_to_index(alpha):
    return ord(alpha) - ord("A")


def dfs(r, c, depth):
    global answer

    curr_alpha_index = alpha_to_index(graph[r][c])
    if pre_road[curr_alpha_index]:
        return

    answer = max(answer, depth)
    visited[r][c] = True
    pre_road[curr_alpha_index] = True
    for d in range(4):
        nr, nc = r+dr[d], c+dc[d]
        if 0 <= nr < R and 0 <= nc < C and not visited[nr][nc]:
            dfs(nr, nc, depth+1)
    visited[r][c] = False
    pre_road[curr_alpha_index] = False


input = lambda: sys.stdin.readline().rstrip()
R, C = map(int, input().split())
graph = [[c for c in input()] for _ in range(R)]

visited = [[False]*C for _ in range(R)]
pre_road = [False]*26
answer = 1
dfs(0, 0, 1)

print(answer)

 

pypy로 겨우 통과했다.

다른 답안을 살펴보니, 비트 연산자와 visited에 중복된 연산을 방지하는 로직이 추가되어 있었다.

이 문제와 비슷한 문제를 찾아봐야겠다.

 

 

---

 

 

텀 프로젝트

https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

 

import sys
sys.setrecursionlimit(100_000)


def dfs(curr):
    members.append(curr)

    n_member = arr[curr]
    visited[curr] = True
    if visited[n_member]:
        if n_member in members:
            selected.extend(members[members.index(n_member):])
            return

    else:
        dfs(n_member)


input = lambda: sys.stdin.readline().rstrip()
answer = []
for _ in range(int(input())):
    n = int(input())
    arr = list(map(lambda x: int(x)-1, input().split()))

    selected = []
    visited = [False] * n
    for i in range(n):
        if not visited[i]:
            members = []
            dfs(i)

    answer.append(n - len(selected))

print(*answer, sep="\n")

dfs의 원소를 기억해야 하는 문제

왠만하면 사용하지 않아야할 선형 탐색을 적용했다. (array.index())

섬세하게 로직을 구현해야 시간 초과가 나지 않는다.

 

 

---

 

 

산책(small)

https://www.acmicpc.net/problem/22868

22868번: 산책 (small)

 

 

from collections import deque
import sys


def go():
    q = deque([(S, 0, [])])
    visited = [False] * (N+1)

    result = None
    while q:
        curr, cost, p = q.popleft()
        if result and cost > result:
            return result

        if curr == E:
            result = cost
            path.append(p)
            continue

        if visited[curr]:
            continue

        visited[curr] = True
        for adj in graph[curr]:
            if not visited[adj]:
                q.append((adj, cost+1, p+[adj]))

    return result


def back():
    q = deque([(E, 0)])
    visited = [False] * (N+1)

    while q:
        curr, cost = q.popleft()
        if curr == S:
            return cost

        if visited[curr]:
            continue

        visited[curr] = True
        for adj in graph[curr]:
            if not visited[adj] and not passed[adj]:
                q.append((adj, cost+1))


def passed_route():
    path.sort()
    for n in path[0]:
        passed[n] = True


input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    if a != b:
        graph[a].append(b)
        graph[b].append(a)
for i in range(1, N+1):
    graph[i].sort()
S, E = map(int, input().split())

answer = 0
path = []
answer += go()
passed = [False] * (N+1)
passed_route()

answer += back()

print(answer)

 

문제의 조건 중에 사전 순으로 앞서는 경로를 택하는 부분이 있다. 이 조건으로 조금 고생했다.

 

이 문제로 배우게 된 점이 2개 있는데,

하나는 리스트를 포함하는 리스트의 기본 정렬은 내부 리스트의 원소의 인덱스가 작은 부분부터 정렬하게 된다.(상식대로 동작한다.)

다른 하나는, bfs를 사용해서 노드를 순회할 때, 기준 노드에서 인접하는 노드로 접근하는 순서에 상관없이 똑같이 동작한다고 생각했지만,

그렇지 않고 먼저 접근한 노드가 visited로 처리되면 다른 노드가 먼저 접근한 노드로 접근할 수 없다.

예를 들면, 1 2 3이 다 연결된 무방향 그래프라고 하고 현재 노드가 1이라고 하면

1의 인접 그래프가 3 2 라고 할 때, 1 -> 3 -> 2는 되지만 1 -> 2 -> 3은 안된다.

따라서 사전 순서를 정확히 해야하는 문제라면, 인접 노드 정보를 정렬할 필요가 있다.

 

 

---

 

 

욕심쟁이 판다

https://www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

 

import sys
sys.setrecursionlimit(250_010)


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


def dfs(x, y, cost):
    global answer

    result = 0
    for d in range(4):
        nx, ny = x+dx[d], y+dy[d]
        if 0 <= nx < n and 0 <= ny < n and graph[x][y] < graph[nx][ny]:
            if visited[nx][ny]:
                result = max(result, visited[nx][ny]+1)
            else:
                result = max(result, dfs(nx, ny, cost+1)+1)
    answer = max(answer, cost+result)

    visited[x][y] = result
    return result


input = lambda: sys.stdin.readline().rstrip()
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

answer = 1
visited = [[0]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            dfs(i, j, 1)

print(answer)

 

dfs와 dp를 합친 문제.

답을 출력하기 위해서 answer를 global로 선언하고, 중복된 계산을 방지하기 위해서 visited를 정의했다.

visited는 현재칸 이후에 진행할 수 있는 최대 칸을 저장한다.

dfs 특성 상, 지나온 경로와 앞으로의 경로가 겹칠 수 있으므로 위와 같은 연산은 주의해야하는데,

조건에 의해 현재보다 큰 값만 나아갈 수 있으므로 위 주의사항을 넘길 수 있다.