2번의 조건때문에 이 문제를 dp로 분류하는 것 같다. 그래프 탐색 문제풀때는 최소, 최대값등 조건에 안맞으면 탐색하지 않도록해서 시간 복잡도를 줄이는 유형이 많으니 주의해야 한다.(특히 이번 문제처럼 방문값 갱신할 때)
최종코드
import sys; input = sys.stdin.readline
sys.setrecursionlimit(10**7)
def is_ragne(nx, ny):
return 0 <= nx < N and 0 <= ny < M
def dfs(x, y, stack):
dist = int(arr[x][y])
for dx, dy in zip(dxs, dys):
nx, ny = x + (dx*dist), y + (dy*dist)
if is_ragne(nx, ny):
# 구멍에 빠지면 나가기
if arr[nx][ny] == "H":
continue
# 현재 지나온길들중에 다시 방문한다면
if (nx, ny) in stack:
return False
# 첫 방문이라면
if visited[nx][ny] == 0:
visited[nx][ny] = visited[x][y] + 1
stack.append((nx, ny))
if not dfs(nx, ny, stack):
return False
stack.pop()
else:
if visited[x][y] + 1 > visited[nx][ny]:
visited[nx][ny] = visited[x][y] + 1
stack.append((nx, ny))
if not dfs(nx, ny, stack):
return False
stack.pop()
return True
# 변수 선언 및 입력
N, M = map(int, input().split())
arr = [list(input().strip()) for _ in range(N)]
dxs, dys = [-1, 0, 1, 0], [0, 1, 0, -1]
visited = [[0]*M for _ in range(N)] # 최대 이동횟수를 기록
stack = [] # 현재 지나온 길 로그들을 기록
# start
x, y = 0, 0
visited[x][y] = 1
stack.append((x, y))
if not dfs(x, y, stack):
print(-1)
else:
ans = 0
for i in range(N):
for j in range(M):
ans = max(ans, visited[i][j])
print(ans)
그래프 재귀 탐색할 때 최대한 코드가 길거나 복잡해지더라도 else를 자제하고 if문을 꼼꼼하게 처리해서 구현해야지 디버깅 할 때 편한 것 같다.
이 문제에서 나는 현재 지나온 길들을 stack =[] 이라는 리스트 변수에 담아서 in연산자로 확인했다. 하지만 만약 방문한 길들이 엄청나게 길어질 수 있는 경우의 문제라면 in연산자는 시간복잡도를 많이 잡아먹기 때문에(O(n)) 지양해야 한다.
