[Python] 백준 #1987 알파벳

📚문제: #1987 알파벳(Gold 4)

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

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

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

입력

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

출력

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

예제 모음

입력1
2 4
CAAB
ADCB

출력1
3

입력2
5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

출력2
6

아이디어

• 새로운 알파벳이 등장하면 방문 처리 및 방문 칸 수를 1증가하고 재귀함수를 호출한다. 인접 알파벳이 이미 방문 처리된 알파벳이면 지나온 칸 수를 갱신하고 해당 함수는 종료한다.

# DFS Algorithm
def DFS(cur, cnt, visited):
    
    global max_cnt
    
    # 4방향
    dr = [-1, 1, 0, 0]
    dc = [0 ,0, -1, 1]
    
    # 현재좌표
    cur_r, cur_c = cur

    for i in range(4):
        
        # 좌표 이동
        move_r, move_c = cur_r + dr[i], cur_c + dc[i]
        
        if 0 <= move_r <= R-1 and 0 <= move_c <= C-1:
            
            # 이동하려는 좌표의 알파벳을 이미 방문한 적 있을 때
            if board[move_r][move_c] in visited:
                
                max_cnt = max(max_cnt, cnt)
            
            # 이동하려는 좌표의 알파벳을 방문한 적 없을 때
            else:
                
                DFS([move_r, move_c], cnt+1, visited+[board[move_r][move_c]])

• 위 코드의 visited 리스트에서 알파벳 존재여부를 조사할 때 O(N)의 시간복잡도가 소요된다. 제출결과 시간초과가 발생하므로 26개의 대문자 알파벳에 대해 방문여부를 체크하는 True/False 리스트로 대체한다. 이 때 재귀함수 호출이 끝나면 해당 알파벳은 미방문(원복) 처리한다.

# DFS Algorithm
def DFS(cur, cnt, visited):
    
    global max_cnt
    
    # 4방향
    dr = [-1, 1, 0, 0]
    dc = [0 ,0, -1, 1]
    
    # 현재좌표
    cur_r, cur_c = cur
    
    for i in range(4):
        
        # 좌표 이동
        move_r, move_c = cur_r + dr[i], cur_c + dc[i]
        
        if 0 <= move_r <= R-1 and 0 <= move_c <= C-1:
            
            # 이동하려는 좌표의 알파벳을 이미 방문한 적 있을 때
            if visited[ord(board[move_r][move_c])-65]:
                
                max_cnt = max(max_cnt, cnt)
            
            # 이동하려는 좌표의 알파벳을 방문한 적 없을 때
            else:
                
                visited[ord(board[move_r][move_c])-65] = True
                DFS([move_r, move_c], cnt+1, visited)
                visited[ord(board[move_r][move_c])-65] = False

전체 코드

import sys

# 전역변수 선언
max_cnt = -1

# DFS Algorithm
def DFS(cur, cnt, visited):
    
    global max_cnt
    
    # 4방향
    dr = [-1, 1, 0, 0]
    dc = [0 ,0, -1, 1]
    
    # 현재좌표
    cur_r, cur_c = cur
    
    for i in range(4):
        
        # 좌표 이동
        move_r, move_c = cur_r + dr[i], cur_c + dc[i]
        
        if 0 <= move_r <= R-1 and 0 <= move_c <= C-1:
            
            # 이동하려는 좌표의 알파벳을 이미 방문한 적 있을 때
            if visited[ord(board[move_r][move_c])-65]:
                
                max_cnt = max(max_cnt, cnt)
            
            # 이동하려는 좌표의 알파벳을 방문한 적 없을 때
            else:
                
                visited[ord(board[move_r][move_c])-65] = True
                DFS([move_r, move_c], cnt+1, visited)
                visited[ord(board[move_r][move_c])-65] = False
                

# R, C가 주어진다.
R, C = map(int, sys.stdin.readline().split())

# 보드 초기화
board = []

for _ in range(R):
    
    board.append(list(sys.stdin.readline().rstrip()))

# DFS Algorithm Execute
start = [0,0]
visited = [False] * (26)
visited[ord(board[0][0])-65] = True
cnt = 1

DFS(start, cnt, visited)

print(max_cnt)