기본적으로 dfs/bfs 알고리즘은
- 노드 방문 -> 방문 처리
- 인접 노드 확인 시 방문 여부 체크한 뒤 미방문 노드만 탐색
이라는 과정을 거친다.
그런데 어떤 문제는 ‘현재 경로에서 방문했는지’를 기준으로 판단하는 경우가 있다. 즉, 전역 방문 배열이 아닌, 경로별로 따로 방문 여부를 관리해야 할 때가 있다.이 때 방문 여부 관리가 진짜 너무 어렵다.
그래서 관련 문제 풀이를 정리해봤다.
DFS
1. 재귀 함수로 방문 단계 전후로 관리
dfs+백트래킹/비트마스킹
백준 1987 - 알파벳 해당 문제에 대한 풀이로
def dfs(row, col, path):
global max_path
max_path = max(max_path, path)
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
for i in range(4):
nr = row + dr[i]
nc = col + dc[i]
if 0 <= nr < r and 0 <= nc < c and not visited[ord(board[nr][nc])-65]:
visited[ord(board[nr][nc])-65] = 1
dfs(nr, nc, path + 1)
visited[ord(board[nr][nc])-65] = 0
return max_pathstack을 함수 안에 두고 반복문을 돌리는 방법 대신 재귀 호출로 해결하며
함수 호출(노드 방문) 전후로 visited를 관리해주었다.
2. 비트마스크로 경로 관리
위와 같은 백준 1987 - 알파벳 문제 풀이로 해당 문제는 방문 처리해야 할 기준점이 알파벳 개수(26개)에 상태가 복잡하지 않아 비트 마스킹으로 경로 방문처리가 가능했다. visited 배열을 따로 두는 대신 재귀함수에 비트마스킹으로 이진수로 표현한 방문여부 나타내는 숫자를 인자로 같이 전달해주었다.
def dfs(row, col, bitmask, path):
global max_path
max_path = max(max_path, path)
for i in range(4):
nr = row + dr[i]
nc = col + dc[i]
if 0 <= nr < r and 0 <= nc < c:
idx = ord(board[nr][nc]) - 65
if not (bitmask & (1 << idx)): # 방문하지 않은 알파벳이라면
dfs(nr, nc, bitmask | (1 << idx), path + 1)3. n차원 배열로 경로 관리
3차원 배열로 방문 여부 관리
백준 2206 - 벽 부수고 이동하기에 대한 풀이로 N * N 사이즈 행렬에서 이동 경로를 벽을 부수고 도착 했는지, 부수지 않고 도착했는지 여부까지 체크해야하는 문제였다.
visited 배열을 N*N*2 사이즈의 3차원 배열을 이용해 경로 별로 벽 부수고 도달/그냥 도달을 따로 체크해줬다.
import sys
from collections import deque
input = sys.stdin.readline
def bfs(sr, sc):
q = deque([(sr, sc, 0, 1)])
visited = [[[0, 0] for _ in range(m)]for __ in range(n)]
# visted[r][c][0] = 벽 안 부수고 옴
# visited[r][c][1] = 랄프했다
visited[sr][sc][0] = 1
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
while q:
r, c, ralph, cnt = q.popleft()
if r == n-1 and c == m-1:
return cnt
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if 0 <= nr < n and 0 <= nc < m:
if board[nr][nc] and not ralph and not visited[nr][nc][1]:
visited[nr][nc][1] = 1
q.append((nr, nc, 1, cnt+1))
elif not board[nr][nc] and not visited[nr][nc][ralph]:
visited[nr][nc][ralph] = 1
q.append((nr, nc, ralph, cnt+1))
return -1
n, m = map(int, input().split())
board = [list(map(int, input().strip())) for _ in range(n)]
print(bfs(0, 0))BFS
4. 노드마다 BFS 돌리기
위에 나온 방법들이 그래프 탐색은 한 번의 일련의 과정으로 진행하되 그 과정에서 방문 여부를 나누어 관리했다면, 하단 문제는 탐색 자체를 여러 번 진행한 문제이다.
N*N배열 위의 아기 상어가 가장 가까운 위치에 있고, 자기보다 작은 물고기만 먹을 수 있을 때 더 이상 먹을 물고기가 없는 상황까지 계속 탐색해야하는 문제이다. 물고기를 여러 번 먹으면 아기 상어가 성장하기 때문에 지점마다 먹을 수 있는 물고기의 범위(방문 가능한 노드)가 계속 달라진다.
때문에
1. 물고기 먹는 함수
2. 가장 가까운 먹을 수 있는 물고기 탐색 함수(BFS)
를 나누어서
- 물고기 먹는 함수 실행
while 먹을 수 있는 물고기 남아있을 때:
BFS로 다음 노드 탐색- 가장 가까운 물고기 찾기(물고기 탐색 BFS 실행)
노드 방문에 따른 경로 처리- 가장 가까운 먹을 수 있는 물고기 탐색하기
- 노드의 value 값 바꾸기(물고기 먹으면 해당 노드 value 0으로 처리)
- 상어 크기 갱신
같은 방식을 사용하였다.
import sys
from collections import deque
input = sys.stdin.readline
dr = [-1, 0, 0, 1]
dc = [0, -1, 1, 0]
# 해당 포인트에서 가장 가까운 물고기 찾기
def bfs(r, c):
global size
visited = [[0] * n for _ in range(n)]
q = deque([(r,c)])
visited[r][c] = 1
fish = []
while q:
cr, cc = q.popleft()
if fish and fish[0][0] < visited[cr][cc]:
continue
for i in range(4):
nr = cr + dr[i]
nc = cc + dc[i]
if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
# 일단 최단 거리 방문 처리(못 감, 갈 수 있으나 못 먹음, 갈 수 있고 먹을 수 있음)
visited[nr][nc] = visited[cr][cc] + 1
if 0 <= arr[nr][nc] <= size[0]: # 갈 수 있음
q.append((nr, nc))
if 0 < arr[nr][nc] < size[0]:
fish.append((visited[cr][cc], nr, nc))
return sorted(fish, key=lambda x : (x[0], x[1], x[2]))
# 물고기 먹기
def eat_fish(r, c):
global size, time
while True:
fish = bfs(r, c)
if not fish:
return time
# 위치 갱신
cnt, r, c = fish[0]
time += cnt
size[1] += 1
arr[r][c] = 0
# 먹은 물고기 위치 0으로
if size[0] == size[1]:
size[0] += 1
size[1] = 0
n = int(input())
arr = []
size = [2, 0]
time = 0
for row in range(n):
temp = list(map(int, input().split()))
if 9 in temp:
sr = row
sc = temp.index(9)
temp[sc] = 0
arr.append(temp)
print(eat_fish(sr, sc))아 어려워~~~
