[백준알고리즘] 1987번: 알파벳 -Python

[백준알고리즘] 1987번: 알파벳 -Python

https://www.acmicpc.net/problem/1987

1987번: 알파벳

20200404. 새로 풀었다. 이번에도 PyPy로만 통과가 가능했다. 처음에는 모양이 달랐는데 계속 시도하다보니 기존 코드와 거의 동일해졌다. 

새로 푼 코드는 맨 아래에 추가해놓았다.

---

이번 문제는 PyPy로 통과했는데, PyPy로도 시간이 꽤 걸렸다.

 

문제는 DFS와 BFS 차이인 것 같다. Python으로 통과한 분들의 코드를 몇 개 봤는데, 다 BFS로 푸셨다.

길이와 관련해서 구하는 경우는 BFS가 대부분 유리한 것 같다.

 

푼 방법은 알파벳의 개수만큼의 크기의 리스트를 설정하고 방문했던 알파벳에 대해서 체크를 해주었다.

import sys

def dfs(i, j, m):
    global ans

    ans = max(ans, m)

    for t in range(4):
        x, y = i + dx[t], j + dy[t]
        if 0<=x<r and 0<=y<c and not alpha[ord(table[x][y]) - 65]:
            alpha[ord(table[x][y]) - 65] = 1
            dfs(x, y, m+1)
            alpha[ord(table[x][y]) - 65] = 0

r, c = map(int, sys.stdin.readline().split())
table = [list(sys.stdin.readline().rstrip()) for _ in range(r)]
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
alpha = [0] * 26 # ASCII A=65 ~ Z=90
alpha[ord(table[0][0]) - 65] = 1
ans = 1

dfs(0, 0, 1)
print(ans)

 

20200404

새로 풀면서 달라진점은 table에 저장할 때부터 map을 이용해 알파벳을 ord()-65에 맵핑시킴으로써 0부터 매칭되도록 했다.

따라서 이후에는 반복적으로 ord()-65 연산을 수행할 필요가 없다.

def solve(x, y, l):
    global ans
    ans = max(ans, l)

    for d in range(4):
        i, j = x + dx[d], y + dy[d]
        if 0<=i<r and 0<=j<c and alpha[table[i][j]] == 0:
            alpha[table[i][j]] = 1
            solve(i, j, l+1)
            alpha[table[i][j]] = 0

r, c = map(int, input().split())
table = [list(map(lambda x: ord(x)-65, input().rstrip())) for _ in range(r)]
dx, dy = (-1, 1, 0, 0), (0, 0, -1, 1)
alpha = [0] * 26
ans = 0

alpha[table[0][0]] = 1
solve(0, 0, 1)
print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다