[코테 알고리즘] DFS, BFS / 관련 문제

본 글은 "나동빈"님의 [이것이 코딩 테스트다]를 참고하여 작성하였으며, 필자가 직접 문제를 풀며 관련된 문제들을 찾아 정리하였습니다.

시리즈 보기
[코테 알고리즘] 파이썬 기본 / 관련 문제
[코테 알고리즘] 파이썬 주요 라이브러리 / 관련 문제
[코테 알고리즘] 그리디 / 관련 문제
[코테 알고리즘] 구현 / 관련 문제
[코테 알고리즘] DFS, BFS / 관련 문제
[코테 알고리즘] 정렬 / 관련 문제
[코테 알고리즘] 다이나믹 프로그래밍 / 관련 문제
[코테 알고리즘] 최단 경로 / 관련 문제
[코테 알고리즘] 그래프 이론 / 관련 문제

 

자료 구조

• 탐색 : 많은 양의 데이터 중 원하는 데이터를 찾는 과정
  • 그래프, 트리 등의 자료구조에서 탐색
  • DFS, BFS 등을 이용
• 트리 구현
  • 인접 행렬
    • 2차원 배열로 그래프의 연결 관계를 표현하는 방식
    • 연결되지 않은 경우 INF의 비용으로 작성
  • 인접 리스트
    • 리스트로 그래프의 연결 관계를 표현하는 방식
    • 2차원 리스트를 이용해 표현

 

재귀함수 사용의 유의사항

• 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 표현 가능
• 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 도 있음
  • 반대도 마찬가지
• 스택을 사용해야할 경우 구현상 스택 라이브러리 대신 재귀 함수를 이용하는 경우가 많음

파이썬 재귀를 이용하는 경우 사용하기

import sys
sys.setrecursionlimit(10 ** 6)

 

DFS

• 스택 자료구조에 기초함
  • 그러나 스택을 사용해 구현할 필요는 없음
  • 재귀 함수를 이용해 간결하게 구현
• 동작 구조
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있다면
     1. 그 노드를 스택에 넣고 방문 처리
     2. 방문하지 않은 인접 노드가 없다면 최상단 노드를 꺼냄
  3. 2번 과정을 더 이상 수행하지 못할 때까지 반복
• O(N)의 시간이 소요됨

def dfs(graph, v, visited):
	# 현재 노드를 방문 처리
	visited[v] = True
	print(v, end=" ")
	# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
	for i in graph[v]:
		if not visited[i]:
			dfs(graph, i, visited)

 

BFS

• 간선의 비용이 모두 같을 때 최단 거리를 탐색할 때 사용하는 알고리즘
  • 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문
• deque 라이브러리를 사용하여 구현
• 동작 구조
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 진행
  2. 큐에서 노드를 꺼낸 뒤에
     1. 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
  3. 2번 과정을 더 이상 수행하지 못할 때까지 반복
• O(N)의 시간이 소요
  • 일반적인 경우 실제 수행시간은 DFS보다 좋은 편

from collections import deque

def bfs(graph, start, visited):
	# 큐 구현
	queue = deque([start])
	# 현재 노드를 방문 처리
	visited[start] = True
	#큐가 빌 때까지 반복
	while queue:
		v = queue.popleft()
		print(v, end=" ")
		# 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
		for i in graph[v]:
			if not visited[v]:
				queue.append(i)
				visited[i] = True

 

문제

신기한 소수 - DFS, 백트래킹, 소수 판단

[백준] 2023번 파이썬 - DFS 풀이

• 소수 판단 코드

# 시간 복잡도를 계산했을 때 이렇게 소수를 판단해도 됨
def isPrime(n):
    for i in range(2, int(n / 2 + 1)):
        if n % i == 0:
            return False
    return True

• 그래프처럼 생각하는 것이 중요
  • 백 트래킹을 이용

import sys
input = sys.stdin.readline

digit = int(input())
# 신기한 소수들을 넣을 리스트
num = [[], [2, 3, 5, 7]]

def dfs(d):
    num.append([])
    for first in num[d]:
        # 짝수는 뒤의 자리수로 추가할 필요가 없으므로 2씩 건너뛰기
        for plus in range(1, 10, 2):
            new = first * 10 + plus
            # 소수임을 판단해서 "신기한 소수"로 추가할지 판단
            if isPrime(new):
                num[d+1].append(new)

# 시간 복잡도를 계산했을 때 이렇게 소수를 판단해도 됨
def isPrime(n):
    for i in range(2, int(n / 2 + 1)):
        if n % i == 0:
            return False
    return True

# 자리수에 해당하는 값까지 리스트를 만들어서 접근
for d in range(1, digit+1):
    dfs(d)

for i in num[digit]:
    print(i)

• 미리 계산해둔 값을 사용한다 & 부모 노드 취급 → 그래프로도 접근할 생각하기

 

 

효율적인 해킹 - BFS

[백준] 1325번 파이썬 - 그래프(BFS), 시간 초과 해결

• 방향 그래프 / 무방향 그래프 구분하기

import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
com = [[] for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    com[a].append(b)

comCnt = [0] *(n+1)

def check(n):
    que = deque()
    que.append(n)
    visited[n] = True
    while que:
        now = que.popleft()
        # 아래 자식 노드들로 가지를 뻗으므로 부모쪽을  + 1
        visited[now] = True
        comCnt[now] += 1
        for new in com[now]:
            if not visited[new]:
                que.append(new)

for i in range(n+1):
    check(i)
    visited = [False] * (n + 1)

tmpMax = max(comCnt)

for idx in range(n + 1):
    if comCnt[idx] == tmpMax:
        print(idx, end=" ")

 

산책 (small) - BFS, 경로 저장

[백준] 2023번 파이썬 - DFS 풀이

• 경로 트래킹에 유의할 것.
• 정렬 순서도 유의할 것….

import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, n+1):
    graph[i].sort()

s, e = map(int, input().split())

def bfs(start, end, visited):
    que = deque()
    que.append((start, 0, str(start)))
    visited[start] = True

    while que:
        now, distance, going = que.popleft()
        if now == end:
            return distance, going
        for new in graph[now]:
            if not visited[new]:
                que.append((new, distance+1, going + " " + str(new)))
                visited[new] = True

visited = [False] * (n+1)
first, go = bfs(s, e, visited)

visited = [False] * (n+1)
for i in list(map(int, go.split())):
    visited[i] = True
visited[s] = False
visited[e] = False

print(first + bfs(e, s, visited)[0])

 

단지 번호 붙이기 (유니온 파인드)

2667번: 단지번호붙이기

import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
graph = [list(map(int, input().rstrip())) for _ in range(n)]
apt = []

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

def bfs(a, b):
    cnt = 1
    que = deque()
    que.append((a, b))
    graph[a][b] = 0
    while que:
        x, y = que.popleft()
        for i in range(4):
            xx = x + dx[i]
            yy = y + dy[i]
            if 0 <= xx < n and 0 <= yy < n and graph[xx][yy] == 1:
                graph[xx][yy] = 0
                que.append((xx, yy))
                cnt += 1
    return cnt

for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            apt.append(bfs(i, j))

apt.sort()
print(len(apt))
for a in apt:
    print(a)

 

봄버맨

16918번: 봄버맨

import sys
input = sys.stdin.readline
from collections import deque

dx = [-1,0,1,0]
dy = [0,1,0,-1]
q = deque()

R,C,N = map(int,input().rstrip().split())

board = []
for _ in range(R):
    board.append(list(input().rstrip()))

# 폭탄이 모두 폭발한다.
def bfs(q,board):
    while q:
        x,y = q.popleft()
        board[x][y] = '.'
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if nx>=0 and nx<R and ny>=0 and ny<C and board[nx][ny] =='O':
                board[nx][ny] = '.'

def simulate(t):
    global q, board
    if t == 1:
        for i in range(R):
            for j in range(C):
                if board[i][j] == 'O':
                    q.append((i,j))
    elif t%2 == 1:
        # 3초가 지난 폭탄을 폭발시킨다.
        bfs(q,board)
        # 3초후에 터질 폭탄을 q에 다시 저장한다.
        for i in range(R):
            for j in range(C):
                if board[i][j] == 'O':
                    q.append((i,j))
    else:
        # 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다.
        board = [['O']*C for _ in range(R)]

for i in range(1,N+1):
    simulate(i)

for i in board:
    print(''.join(i))

 

숨바꼭질 3

13549번: 숨바꼭질 3

from collections import deque
MAX = 100001
check = [False] * MAX
dist = [-1] * MAX

n,k = map(int, input().split())
q = deque()
q.append(n)
check[n] = True
dist[n] = 0

while q:
    now = q.popleft()
    if now*2 <= MAX and check[now*2] == False:  # 순간이동
        q.appendleft(now*2)
        check[now*2] = True
        dist[now*2] = dist[now]
    if now + 1 <= MAX and check[now+1] == False: # x+1이동
        q.append(now+1)
        check[now+1] = True
        dist[now+1] = dist[now] + 1
    if now - 1 >= 0 and check[now-1] == False: # x-1이동
        q.append(now-1)
        check[now-1] = True
        dist[now-1] = dist[now] + 1
print(dist[k])

 

불!

4179번: 불!

from sys import stdin
from collections import deque

input = stdin.readline

R, C = map(int, input().split())
graph = []

pos_j = []  # 지훈 위치
pos_f = []  # 불 위치
for i in range(R):
    tmp = list(input())
    for j in range(C):
        if tmp[j] == "J":
            pos_j.append((i, j))
        elif tmp[j] == "F":
            pos_f.append((i, j))
    graph.append(tmp)

q = deque()
q.append((pos_j[0][0], pos_j[0][1], "J"))  # 지훈이가 먼저 이동
graph[pos_j[0][0]][pos_j[0][1]] = 0

if len(pos_f) != 0:
    for (r, c) in pos_f:
        q.append((r, c, "F"))
        graph[r][c] = "#"

def bfs():
    dx = [-1, 1, 0, 0]  # 상하좌우
    dy = [0, 0, -1, 1]
    while q:
        x, y, case = q.popleft()
        if case == "J" and (x == 0 or y == 0 or x == R - 1 or y == C - 1):  # 탈출가능
            if graph[x][y] == "#":
                continue
            return graph[x][y] + 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < R and 0 <= ny < C:
                if graph[nx][ny] != "#" and case == "F":
                    graph[nx][ny] = "#"
                    q.append((nx, ny, "F"))
                elif graph[nx][ny] == "." and case == "J" and graph[x][y] != "#":
                    graph[nx][ny] = graph[x][y] + 1
                    q.append((nx, ny, "J"))
    return "IMPOSSIBLE"

print(bfs())