이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 64 번째 글 입니다.
목차
골드4 : 완전 탐색 문제이다.
풀이
이게 전날에 급하게 짜다가 조건을 놓친 문제인데, 오늘의 첫문제로 도전해보았다. 난 BFS로 문제 풀이방향을 정했는데, 문제가 방문이 중복으로 일어난다는 것이다. 처음에는 이전의 발판들을 기억하고 오니까, 각각에 도착하는 방법의수가 다르기 때문에 문제가 없을 것이라 생각했다. 하지만 아래의 경우 중복이 매우 많이 발생할 여지가 있다.
ABEA
BCDE
ADEF
이 문제는 결국, 특정 지역에 최소로 몇번만에 도착했냐가 궁금한 것이 아니고, 그냥 얘가 밟고 지나온 것이 어떤 것이냐, 그리고 그게 길이가 얼마냐가 중요한 문제이다. 그래서 탐색하는 순서는 상관이 없고, 모두 탐색하기만 하면 된다.
그런데 그 과정에서 중복이 발생할 여지가 있기 때문에 이러한 부분을 제거하면서 찾아야 한다. 그렇기 때문에 이 문제에서는 queue말고 set을 써서 구현해도 문제가 없다. queue를 쓴다면 중복제거를 해야하는데 굉장히 귀찮다.
Code
# BFS로 최단거리를 구하는 것이 아니기 때문에 굳이 queue일 필요가 없다.
# 순서에 상관없이 완전 탐색을 하는 것이 목적!!
import sys
from collections import deque
input = sys.stdin.readline
r, c = map(int, input().split())
graph = [list(map(str, input().rstrip())) for _ in range(r)]
d = [[1, 0], [0, 1], [-1, 0], [0, -1]]
max_value = 0
q = set()
q.add((0, 0, graph[0][0]))
while q:
cy, cx, memory = q.pop()
max_value = max(max_value, len(memory))
for dy, dx in d:
ny, nx = cy + dy, cx + dx
if 0 <= ny < r and 0 <= nx < c and graph[ny][nx] not in memory:
q.add((ny, nx, memory + graph[ny][nx]))
print(max_value)