1️⃣ 서론
백준 문제 1987번 알파벳 입니다. 파이썬(Python)으로 풀었습니다.
2️⃣ 문제 설명
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있습니다.
보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있습니다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 합니다.
즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없습니다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하는 문제입니다.
3️⃣ 풀이
이 문제는 dfs로 해결이 가능한 문제입니다. 알파벳이 중복되지 않고 최대한 많은 칸을 뚫은다면 답이 될 수 있습니다.
방문처리를 알파벳을 지나갔는지 안지나갔는지로 하면 따로 vis 배열을 만들 필요없이 방문 처리 검사를 할 수 있었습니다.
그럼 소스코드를 보시겠습니다.
4️⃣ 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import sys
input = sys.stdin.readline
r, c = map(int, input().split())
arr = [list(map(lambda x: ord(x) - 65, input().rstrip())) for _ in range(r)]
alpha = [0] * 26
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def dfs(x, y, count):
global ans
ans = max(ans, count)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c and alpha[arr[nx][ny]] == 0:
alpha[arr[nx][ny]] = 1
dfs(nx, ny, count + 1)
alpha[arr[nx][ny]] = 0
ans = 1
alpha[arr[0][0]] = 1
dfs(0, 0, 1)
print(ans)
5️⃣ 마치며..
질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️
