[BOJ] 1987 / 알파벳 / Python 파이썬

[BOJ] 1987 / 알파벳 / Python 파이썬

[BOJ] 1987 / 알파벳 / Python 파이썬

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

1987번: 알파벳

 

풀이

시간 조건이 굉장히 빠듯하다고 느꼇던 백트레킹 문제였다.

 

최장거리 경로탐색과 비슷하지만, 알파벳을 기록하는 부분에서 시간초과가 발생하였다.

 

다른분들의 풀이를 참고하니, dequeue 가 아닌 set 을 이용한 bfs 로 동작시간을 단축 하던가,

알파벳을 숫자로 변화하여 visited 로 처리하였는데 후자의 경우로 풀어보았다.

 

 

 

import sys
input = sys.stdin.readline

R, C = map(int, input().split())

maps = []

for _ in range(R):
    maps.append(list(input().rstrip()))

x = y = 0

res = 0

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

visited = [0] * 26
visited[ord(maps[0][0]) - 65] = 1


def DFS(y, x, cnt):
    global res, R, C
    res = max(res, cnt)

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

        if 0 <= Y < R and 0 <= X < C and not visited[ord(maps[Y][X]) - 65]:
            visited[ord(maps[Y][X]) - 65] = 1
            DFS(Y, X, cnt+1)
            visited[ord(maps[Y][X]) - 65] = 0


DFS(y, x, 1)
print(res)

 

 

---

참고 블로그

 

DFS 풀이

https://it-garden.tistory.com/272

백준알고리즘 - 1987번 알파벳 - 파이썬(Python)

 

 

BFS 풀이

https://velog.io/@bye9/%EB%B0%B1%EC%A4%80%ED%8C%8C%EC%9D%B4%EC%8D%AC-1987-%EC%95%8C%ED%8C%8C%EB%B2%B3

[백준/파이썬] 1987 알파벳