백준 1987번 알파벳

https://www.acmicpc.net/problem/1987
실패이유: 시간초과, 메모리초과

• 시간초과 코드

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def go(x, y, pick: list, cnt):
    pick = pick + [board[y][x]]

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if board[ny][nx] not in pick:
                go(nx, ny, pick, cnt + 1)

    moves.append(cnt)


moves = []
h, w = map(int, input().split())
board = [list(input()) for _ in range(h)]

go(0, 0, [], 1)

print(max(moves))

• if board[ny][nx] not in pick:
  • 이 부분에서 시간초과 발생

• 메모리 초과 코드

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def go(x, y, cnt):
    check[ord(board[y][x]) - ord('A')] = True

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if not check[ord(board[ny][nx]) - ord('A')]:
                go(nx, ny, cnt + 1)

    check[ord(board[y][x]) - ord('A')] = False
    moves.append(cnt)


moves = []
h, w = map(int, input().split())
board = [list(input()) for _ in range(h)]
check = [False] * 26

go(0, 0, 1)
print(max(moves))

moves.append(cnt) 로 모든 경우의 수를 moves 리스트에 추가하는 경우, 메모리 초과 발생

• 정답 코드

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def go(x, y):
    check[ord(board[y][x]) - ord('A')] = True
    ans = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if not check[ord(board[ny][nx]) - ord('A')]:
                ans = max(go(nx, ny), ans)

    check[ord(board[y][x]) - ord('A')] = False
    return ans + 1


h, w = map(int, input().split())
board = [list(input()) for _ in range(h)]
check = [False] * 26

print(go(0, 0))

• 모든 경우의 수를 moves 리스트에 더하지 않고, return ans + 1 로 값을 반환하도록 변경
  • ans + 1 을 반환하는 것은, 현재 칸을 밟았음을 의미한다.
• ans = max(go(nx, ny), ans) 를 통해, 가장 큰 값 (가장 멀리간 값) 을 ans 에 할당

출처: 코드플러스 - 알고리즘 중급 1/3 강의
https://code.plus/course/43