[백준] 1987 - 알파벳

1. 문제

1987번: 알파벳

2. 개요

알파벳 대문자가 각 칸마다 쓰여져있는 보드를 중복되는 문자 없이 이동할 수 있는 최대 거리를 구하는 문제.

3. 코드 및 추가내용

import sys

R, C = map(int, sys.stdin.readline().split())

board = []
for i in range(R):
    board.append(list(sys.stdin.readline().rstrip()))

ans = 1
def dfs(visited = [['' for i in range(C)] for j in range(R)], y = 0, x = 0, depth = 1):
    global ans
    _visited = visited
    if y == x == 0:
        _visited[0][0] = board[0][0]

    dirY, dirX = [-1, 0, 1, 0], [0, -1, 0, 1]

    for i in range(4):
        nextY, nextX = y + dirY[i], x + dirX[i]

        if nextY < 0 or nextY >= R or nextX < 0 or nextX >= C:
            continue
        if board[nextY][nextX] in _visited[y][x]:
            continue

        _visited[nextY][nextX] = _visited[y][x] + board[nextY][nextX]
        ans = max(ans, len(_visited[nextY][nextX]))
        dfs(_visited, nextY, nextX)

dfs()
print(ans)

첫 시도.

예제 답은 잘 나왔으나 시간초과.

global활용이 좋지 않다는 얘기를 들었어서 그 문제인가 싶어서 일단 제일 먼저 건드려봤다.

import sys

R, C = map(int, sys.stdin.readline().split())

board = []
for i in range(R):
    board.append(list(sys.stdin.readline().rstrip()))

def dfs(visited = [['' for i in range(C)] for j in range(R)], y = 0, x = 0, depth = 1):
    k = depth
    _visited = visited
    if y == x == 0:
        _visited[0][0] = board[0][0]

    dirY, dirX = [-1, 0, 1, 0], [0, -1, 0, 1]

    for i in range(4):
        nextY, nextX = y + dirY[i], x + dirX[i]

        if nextY < 0 or nextY >= R or nextX < 0 or nextX >= C:
            continue
        if board[nextY][nextX] in _visited[y][x]:
            continue

        _visited[nextY][nextX] = _visited[y][x] + board[nextY][nextX]
        k = max(k, dfs(_visited, nextY, nextX, depth + 1))

    return k

k = dfs()
print(k)

2차 시도.

똑같이 pypy로도 시간초과.

문자열 저장 + in활용으로 인한 시간초과일거라 생각하고 재수정

import sys

R, C = map(int, sys.stdin.readline().split())

board = []
for i in range(R):
    board.append(list(sys.stdin.readline().rstrip()))

def dfs2(visited = [[0 for i in range(C)] for j in range(R)], y = 0, x = 0, depth = 1, alpha = [0 for l in range(26)]):
    k = depth
    _visited = visited
    _alpha = alpha
    if y == x == 0:
        _visited[0][0] = 1
        _alpha[ord(board[0][0]) - ord("A")] = 1

    dirY, dirX = [-1, 0, 1, 0], [0, -1, 0, 1]

    for i in range(4):
        nextY, nextX = y + dirY[i], x + dirX[i]

        if nextY < 0 or nextY >= R or nextX < 0 or nextX >= C:
            continue
        if _visited[nextY][nextX]:
            continue
        if alpha[ord(board[nextY][nextX]) - ord("A")]:
            continue
        
        _visited[nextY][nextX] = 1
        _alpha[ord(board[nextY][nextX]) - ord("A")] = 1
        k = max(k, dfs2(_visited, nextY, nextX, depth + 1, _alpha))

    visited[y][x] = 0
    _alpha[ord(board[y][x]) - ord("A")] = 0
    return k

b = dfs2()
print(b)

각 문자가 사용되었는지를 판별할 alpha배열을 새로 만들어 겨우겨우 해결.

그래도 시간은 엄청 오래걸렸다..