[알고리즘][Python] 백준 1987 알파벳 문제 풀이

문제 출처 : www.acmicpc.net/problem/1987

1987번: 알파벳

---

문제 해석 : 말이 움직일 수 있는 최대 길이의 경로를 탐색한다. 여기서 바닥에 적힌 알파벳은 한번씩만 방문 가능하다. 이때의 최대 경로 길이를 반환하는 문제이다.

 

문제 풀이 :  DFS로 문제를 풀이하면서 alpha_table을 통해서 이미 방문한 적이 있는지 없는지를 검사한다. 계속해서 변환하는 작업을 줄이기 위해 테이블을 입력 받을 때 map(ord(x)-65, input().strip())을 통해서 한번에 모두 숫자로 변환해 준다. 나머지 과정은 DFS와 조건 탐색으로 마무리 하면 된다.

---

풀이 코드

import sys
input = sys.stdin.readline

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


def solution(count, a, b):
    global answer
    global visited_alpha

    answer = max(answer, count)
    x, y = a, b
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < R and 0 <= ny < C and visited_alpha[alpha_map[nx][ny]] is False:
            visited_alpha[alpha_map[nx][ny]] = True
            solution(count+1, nx, ny)
            visited_alpha[alpha_map[nx][ny]] = False

R, C = map(int, input().split())
alpha_map = [list(map(lambda x: ord(x) - 65, input().strip())) for _ in range(R)]

answer = 1
visited_alpha = [False] * 26
visited_alpha[alpha_map[0][0]] = True
solution(1,0,0)

print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.