[Python] 백준1987 알파벳

12 Jun 2023 in Study on Algorithm

백준1987 알파벳 링크

문제

예제 입력

---

코드

import sys
input = sys.stdin.readline

R, C = map(int, input().split())
arr = []
for _ in range(R):
    arr.append(list(map(lambda x: ord(x) - ord('A'), input())))

def backt(y, x, cnt):
    global ans
    ans = max(ans, cnt)

    for i in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        newx = x + i[0]
        newy = y + i[1]

        if 0 <= newx < C and 0 <= newy < R:
            if not visit[arr[newy][newx]]:
                visit[arr[newy][newx]] = True
                backt(newy, newx, cnt+1)
                visit[arr[newy][newx]] = False

ans = 0
visit = [False] * 26
# visit[ord(arr[0][0]) - 65] = True
visit[arr[0][0]] = True
backt(0, 0, 1)
print(ans)

설명

파이썬을 통해서 사용자로부터 입력받아 빽트래킹(DFS) 알고리즘으로 사용하여 알파벳를 구현했습니다.

---

정리

visit = [[0] * C for _ in range(R)]
def bfs():
    q = deque()
    q.append([[0, 0], arr[0][0]]) # 0, 0 'C'
    visit[0][0] = 1

    while q:
        pos, val = q.popleft()
        for i in [[1, 0], [0, -1], [-1, 0], [0, 1]]:
            newx = pos[0] + i[0]
            newy = pos[1] + i[1]

            if 0 <= newx < C and 0 <= newy < R:
                for v in val:
                    if arr[newy][newx] == v:
                        break
                else:
                    if visit[newy][newx] < visit[pos[1]][pos[0]] + 1:
                        visit[newy][newx] = visit[pos[1]][pos[0]] + 1
                        q.append([[newy, newx], val+arr[newy][newx]])

bfs()
print(max(map(max, visit)))

처음에는 BFS로 해결하려고 했으나 연쇄적으로 일어나는 연산에서 기억을 하기 어렵기 때문에 DFS로 한 가지 경우씩 해결하고 알파벳 조건은 배열로 저장하여 빽트래킹 가능하게 만드는 것이 힘들었습니다.

---

결과