[SWEA] #1824 혁진이의 프로그램 검증

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx

풀이 방법

1. 주어진 문자에 따라 각 명령을 수행하는 함수 작성
2. @가 있을 때만 프로그램을 멈출 수 있으므로 격자판에 @가 있을 때만 함수 실행하도록 조건 추가
3. 메모리에 저장된 값을 계산하는 문자(+, -)의 경우 값 계산 후 16으로 나눠주고, 주어진 격자판 밖으로 이동하는 경우 x, y 좌표 값을 각각 R, C로 나눠줌
4. 최대 재귀 깊이 이상으로 호출되어 에러가 나는 경우를 해결하기 위해 visited 리스트 추가 -> 같은 좌표에 같은 값, 같은 방향으로 방문한 적이 있으면 리턴
5. 테스트 케이스 40번에서 오답(NO)이 나옴 -> 확인해보니 @가 ^, v, <, >로 둘러싸여 있어서 @와 맞닿아있는 칸의 개수와 해당 칸들에 이 4가지 문자가 있는 개수가 같을 경우 함수 실행하지 않도록 조건 추가

코드

delta = [[0, 1], [1, 0], [-1, 0], [0, -1]]  # 우 하 상 좌
arrows = {
    '<': 3,
    '>': 0,
    '^': 2,
    'v': 1,
}


def next_x(x):
    return x % R


def next_y(y):
    return y % C


def go(nx, ny, val, drt):
    global result, func_stop, check_stop

    now = command[nx][ny]
    key = str(nx) + str(ny) + str(val) + str(drt)
    # 최대 재귀 깊이 이상으로 호출되는 것을 막기 위함
    if key in visited:
        return
    else:
        visited.append(key)
    # @를 발견한 이후의 함수 호출에 대해서는 바로 바로 리턴 -> 실행시간 1/4로 감소
    if check_stop:
        return

    if now == '@':
        result = 'YES'
        check_stop = True
        return
    elif now == '.':
        go(next_x(nx + delta[drt][0]), next_y(ny + delta[drt][1]), val, drt)
    elif now in arrows:
        go(next_x(nx + delta[arrows[now]][0]), next_y(ny + delta[arrows[now]][1]), val, arrows[now])
    elif now == '_':
        if val == 0:
            go(next_x(nx + delta[0][0]), next_y(ny + delta[0][1]), val, 0)
        else:
            go(next_x(nx + delta[3][0]), next_y(ny + delta[3][1]), val, 3)
    elif now == '|':
        if val == 0:
            go(next_x(nx + delta[1][0]), next_y(ny + delta[1][1]), val, 1)
        else:
            go(next_x(nx + delta[2][0]), next_y(ny + delta[2][1]), val, 2)
    elif now == '?':
        for i in range(4):
            go(next_x(nx + delta[i][0]), next_y(ny + delta[i][1]), val, i)
    elif now == '+':
        go(next_x(nx + delta[drt][0]), next_y(ny + delta[drt][1]), (val + 1) % 16, drt)
    elif now == '-':
        go(next_x(nx + delta[drt][0]), next_y(ny + delta[drt][1]), (val - 1 + 16) % 16, drt)
    else:
        go(next_x(nx + delta[drt][0]), next_y(ny + delta[drt][1]), int(now), drt)


T = int(input())
for tc in range(1, T+1):
    R, C = map(int, input().split())
    command = [input() for _ in range(R)]
    visited = []
    result = 'NO'
    check_stop = False
    func_stop = False

    keyx, keyy = 0, 0
    for row in range(R):
        if '@' in command[row]:
            for col in range(C):
                if command[row][col] == '@':
                    keyx = row
                    keyy = col
            check_stop = True
            break

    # tc 40 처리: @가 화살표로 둘러싸여서 접근할 수 없으면 함수 호출 안 함
    limit = 0
    check = 0
    for d in delta:
        cx = keyx + d[0]
        cy = keyy + d[1]
        if 0 <= cx < R and 0 <= cy < C:
            limit += 1
            if command[cx][cy] in arrows:
                check += 1
    if check_stop and limit != check:
        check_stop = False
        go(0, 0, 0, 0)

    print('#{} {}'.format(tc, result))