[백준/BOJ] gold4 - 1987번 알파벳 (Python)

▶1987 - 알파벳

▶문제

세로 R 칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

 

▶입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R, C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

 

▶출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

▶예제

 

▶풀이

dfs로 풀면 간단하게 해결할 수 있는 문제이다.

거기에 alpha라는 set을 설정해서 지나간 알파벳을 저장해 두고 한 번만 지나도록 설정했다.

그렇게 dfs로 돌리면서 조건에 성립하면 cnt를 늘리면서 결과를 만들어냈다.

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


def dfs(x, y, cnt):
    global result
    result = max(result, cnt)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < r and 0 <= ny < c and \
                not maps[nx][ny] in alpha:
            alpha.add(maps[nx][ny])
            dfs(nx, ny, cnt + 1)
            alpha.remove(maps[nx][ny])


r, c = map(int, input().split())

maps = []
for i in range(r):
    maps.append(list(input()))

result = 0
alpha = set()
alpha.add(maps[0][0])

dfs(0, 0, 1)
print(result)

종종 python3로 제출해서 시간 초과, 메모리 초과가 뜨는 경우가 많은 거 같다.

pypy3로 제출하면 다 정답이 나오지만 뭔가 찝찝한 건 사실이다.

백준에서 python3로 정답을 맞힌 사람을 검색해보니 충분히 있다.

내가 더 노력해서 python3로도 정답을 맞힐 수 있게 노력해야겠다.

60점 남았다. 세 문제만 더 풀면 class 5를 얻어서 50점을 한 번에 채울 수 있다.

열심히 해보자!