백준 1987번 알파벳 파이썬

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

예제 입력 1

2 4
CAAB
ADCB

예제 출력 1

3

정답 답안 블로그

import sys
input = lambda: sys.stdin.readline().strip()

r,c=map(int,input().split())
a=[list(map(lambda x : ord(x)-65, input())) for i in range(r)]
ch=[0] * 26 # 26은 알파벳 개수

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

def dfs(x, y, z):
    global answer
    answer=max(answer, z)

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

        if 0 <= nx < r and 0 <= ny < c and ch[a[nx][ny]] == 0:
                ch[a[nx][ny]] = 1
                dfs(nx, ny, z+1)
                ch[a[nx][ny]] = 0

answer=1
ch[a[0][0]] = 1
dfs(0, 0, answer)

print(answer)

• 아스키 코드로 변환하여 딕셔너리로 저장하고 Fasle로 초기화 한다음 방문하면 True로 바꿔서 cnt를 늘리는 방법을 생각했었는데 틀렸다. 접근하면서 이거는 풀 수 있겠다라는 문제와 아무리 생각해도 안 되는 문제가 있는데 dsf와 bfs가 그렇다. 그래서 구글링했다.
• 우선 정답답안은 모든 문자를 만든거보다 들어오는 단어를 아스키 코드로 바꿔서 저장하였다. 그 다음에 그 아스키코드에서 65를 빼면 해당 ch에 만들어진 리스트에 인덱스를 가지게 된다.
• dfs를 돌면서 해당 문자 인덱스를 방문하며 0이면 1로바꿔서 다시 dfs를 돈다. 여기서 문제는 가로와 세로시작에 따라 값이 달라진다. 그래서 answer를 계속 가져간다. dfs가 끝나면 다시 1을 0으로 초기화해줘야 가로로 갔었을때와 세로로 갔었을때 비교가 가능하다. 그렇게 해서 다 돌면 최종적으로 정답이 나온다.