SW Expert Academy 1824. 혁진이의 프로그램 검증

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx&categoryId=AV4yLUiKDUoDFAUx&categoryType=CODE

SW Expert Academy

이 문제를 깊이 우선 탐색(dfs)을 활용하여 풀었다. 처음에 풀었을 때는 잘 안 풀려서 일주일 정도를 다른 문제들을 풀고 나서 다시 풀게 된 문제이다. 이 문제를 풀게 되면서 알게 된 것은 dfs는 재귀를 사용하지 않고도 스택(stack)을 통해서도 구현이 가능하다는 것을 알게 되었다. 물론 재귀를 하였을 때와 탐색하는 순서는 다르지만, 결과는 같다. 다음은 내가 해결한 코드이다.

def solution(map1, visit, test, r, c):
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    stack = [[0, 0, 3, 0]]
    while stack:
        x, y, d, m = stack.pop()
        if visit[x][y][d][m] == test:
            continue
        else:
            visit[x][y][d][m] = test
            if map1[x][y] == '<' or (map1[x][y] == '_' and m != 0):
                stack.append([(x + dx[1]) % r, (y + dy[1]) % c, 1, m])
            elif map1[x][y] == '>' or (map1[x][y] == '_' and m == 0):
                stack.append([(x + dx[3]) % r, (y + dy[3]) % c, 3, m])
            elif map1[x][y] == '^' or (map1[x][y] == '|' and m != 0):
                stack.append([(x + dx[0]) % r, (y + dy[0]) % c, 0, m])
            elif map1[x][y] == 'v' or (map1[x][y] == '|' and m == 0):
                stack.append([(x + dx[2]) % r, (y + dy[2]) % c, 2, m])
            elif map1[x][y] == '@':
                return True
            elif map1[x][y] == '+':
                stack.append([(x + dx[d]) % r, (y + dy[d]) % c, d, (m + 1) % 16])
            elif map1[x][y] == '-':
                stack.append([(x + dx[d]) % r, (y + dy[d]) % c, d, (m - 1) % 16])
            elif map1[x][y] == '.':
                stack.append([(x + dx[d]) % r, (y + dy[d]) % c, d, m])
            elif map1[x][y] == '?':
                for i in range(4):
                    stack.append([(x + dx[i]) % r, (y + dy[i]) % c, i, m])
            else:
                stack.append([(x + dx[d]) % r, (y + dy[d]) % c, d, int(map1[x][y])])
    return False


t = int(input())
visit = [[[[0 for _ in range(16)] for _ in range(4)] for _ in range(20)] for _ in range(20)]
for test in range(1, t + 1):
    r, c = map(int, input().split())
    map1 = [input() for _ in range(r)]
    answer = solution(map1, visit, test, r, c)
    if answer==True:
        answer='YES'
    else:
        answer='NO'
    print('#{} {}'.format(test,answer))