dfs, bfs 카테고리의 골드 4문제이며, 일반적인 bfs방식으로 접근 후 해결이 안된다는 것을 확인하고, 백트래킹과 dfs를 활용한 방식의 풀이로 접근해야 했기에 사고 과정을 정리해보고자 한다.
가장 먼저 접근했던 방식은 일반적인 bfs의 문제풀이였다.
주어진 세로와 가로 길이 만큼의 input graph와 해당 노드를 탐색할때 1씩 증가하는 똑같은 size의 count 그래프, 알파벳 길이만큼의 visited 배열은 만들어줬고, 유니코드의 ord() - 65로 전체 알파벳길이의 인덱스에 접근할 수 있도록 설정해 주었다.
def bfs(x, y):
queue = deque()
queue.append((x,y))
visited[ord( graph[x][y] ) - 65] = True
count[x][y] += 1
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= r or ny >= c:
continue
if visited[ ord(graph[nx][ny]) - 65] :
continue
if not visited[ ord(graph[nx][ny]) - 65]:
visited[ord(graph[nx][ny]) - 65] = True
count[nx][ny] = count[x][y] + 1
queue.append( (nx, ny))
이때 콘솔창에서 확인할 수 있었던 bfs방식의 문제점은 bfs 내부의 queue에 다음으로 탐색할 노드인 nx,ny의 순서에 따라서 방문이 결정되지 않을 노드가 발생할 수 있고 결과적으로 그 선택으로 인해 최적의 해를 도출하게 되지 못한다는 것이었다.
이러한 경우에 사용하는 방식이 바로 백트래킹이다.
백트래킹
정의 : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 차를 찾아가는 기법.
가능한 모든 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것.
즉, 답이 될만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 피하고, 가치지기 하는 것.
주로 문제풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황인 경우에 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현함.
- 해가 될 가능성이 있는 걸 유망(promising)하다고 표현,
- 유망하지 않은 노드에 가지 않는 것을 가지치기(prunning)한다고 표현함.
def bfs(x, y):
queue = deque()
queue.append((x,y))
visited[ord( graph[x][y] ) - 65] = True
count[x][y] += 1
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= r or ny >= c:
continue
if visited[ ord(graph[nx][ny]) - 65] :
continue
if not visited[ ord(graph[nx][ny]) - 65]:
visited[ord(graph[nx][ny]) - 65] = True
count[nx][ny] = count[x][y] + 1
#visited[ord(graph[nx][ny])- 65] = True
queue.append( (nx, ny))다시 문제로 돌아와서, 해당문제에서 고려해야되는 조건은 count가 최대가 될 조건이다. 따라서, 한노드씩 dfs로 탐색을 하며 이때 기존의 answer보다 더 큰 ans로 탐색되는 경우의 수를 발견한 경우에는 visited 배열을 초기화(이전의 시점으로 돌아와서)하고 다시 탐색을 시작하였다.
전체 소스 코드는 다음과 같다.
import sys
from collections import deque
r, c = map(int, sys.stdin.readline().split())
graph = [list(sys.stdin.readline().rstrip()) for i in range(r)]
count = [[0 for i in range(c)] for j in range(r)]
#행렬상에서 이동 기준상 하 좌 우
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
visited = [False]*26
def bfs(x, y):
queue = deque()
queue.append((x,y))
visited[ord( graph[x][y] ) - 65] = True
count[x][y] += 1
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= r or ny >= c:
continue
if visited[ ord(graph[nx][ny]) - 65] :
continue
if not visited[ ord(graph[nx][ny]) - 65]:
visited[ord(graph[nx][ny]) - 65] = True
count[nx][ny] = count[x][y] + 1
queue.append( (nx, ny))
def dfs(x, y, ans):
global answer, visited
answer = max(ans, answer)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# index 벗어나지 않는지 체크하고, 새로운 칸이 중복되는 알파벳인지 체크
if ((0 <= nx < r) and (0 <= ny < c)) and (not visited[ ord(graph[nx][ny]) - 65]):
visited[ord(graph[nx][ny]) - 65] = True
dfs(nx, ny, ans + 1)
# 이전 시점으로 초기화
visited[ord(graph[nx][ny]) - 65] = False
answer = 1
visited[ ord(graph[0][0]) - 65] = True
dfs(0, 0, answer)
"""
잘못된 접근 : bfs
bfs(0,0)
for g in count:
print(g)
"""
print(answer)