[Python][백준] 1987. 알파벳 / 백트래킹,DFS (G4)

🔗링크 :  

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

---

🗒️파이썬 코드 풀이

R,C = map(int,input().split())
lst = []
for i in range(R):
    tmp = list(input())
    lst.append(tmp)

di,dj = [0,1,0,-1],[1,0,-1,0]
alphabet = [0] * 26
alphabet[ord(lst[0][0])-65] = 1

mx = 0
def dfs(i,j,count):
    global mx
    mx = max(mx,count)

    for k in range(4):
        ni,nj = i+di[k],j+dj[k]
        if 0<=ni<R and 0<=nj<C:            
                if not(alphabet[ord(lst[ni][nj])-65]):
                    alphabet[ord(lst[ni][nj])-65] = 1
                    dfs(ni,nj,count+1)
                    alphabet[ord(lst[ni][nj])-65] = 0

dfs(0,0,1)
print(mx)

 

1. BFS를 먼저 생각해보았지만, 알파벳 체크 부분이 안돼서 DFS로 넘어간다. 

 

2. 방문체크 리스트 대신 alphabet을 이용하여 방문 체크를 한다.

 

3. 일반적인 dfs 백트래킹과 똑같은데, alphabet 처리가 좀 독특하다.

 

4. dfs 매개변수로 현재 좌표값과 count 값을 넘겨준다. 

 

 

📌  문제 코멘트

해당 코드를 python으로 하면 안되고, pypy3로 해야한다. 

굳이 ..?! 라는 생각이 든다 ... 

 

뭐 이렇게까지 시간초과를 잡을 필요는 없다고 생각하는데,

방문 표시가 좀 독특해서 블로그 포스팅을 해보았다. 

 

(참고로 방문 표시를 visited와 같이 투머치하게 했어서 메모리 초과도 떴었다...)

---

📚문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

2 4
CAAB
ADCB

예제 출력 1 복사

3

예제 입력 2 복사

3 6
HFDFFB
AJHGDH
DGAGEH

예제 출력 2 복사

6

예제 입력 3 복사

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

예제 출력 3 복사

10