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

🥚문제

---

🥚입력/출력

---

🍳코드

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
# 알파벳 대문자 -> 아스키 코드값 - 65로 바꾸어 저장
board = [list(map(lambda x: ord(x) - 65, list(input().strip())))
         for _ in range(r)]

# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 최대 칸 수를 저장
max_ans = 0

def dfs(row, col, ans):

    global max_ans
    max_ans = max(max_ans, ans)

    for i in range(4):
        new_row = row + dx[i]
        new_col = col + dy[i]
        if 0 <= new_row < r and 0 <= new_col < c:
            if visited[board[new_row][new_col]] == 0:
                # 방문 처리
                visited[board[new_row][new_col]] = 1
                # dfs 수행
                dfs(new_row, new_col, ans + 1)
                # 방문 처리 해제
                visited[board[new_row][new_col]] = 0

# 알파벳 개수만큼의 visited 리스트를 생성
visited = [0]*26
visited[board[0][0]] = 1

# 첫 칸 (0, 0)에서부터 탐색 시작
# 첫 칸도 칸 수에 포함되므로 ans = 1로 설정
dfs(0, 0, 1)
print(max_ans)

---

🧂아이디어

• dfs, 백트래킹
  • 방문 처리를 해주고 dfs 수행한 뒤, 다시 방문 처리를 해제해주기 ⭐⭐⭐⭐⭐
  • Python3로는 '시간초과', Pypy3로 통과

• 방문한 알파벳들을 기록하는 방법
  • 처음에는 리스트에 방문한 알파벳을 넣고, in을 사용하여 검사했는데, in은 모든 리스트를 순회하기 때문에 효율적이지 X
  • 길이가 26(알파벳 개수)인 리스트를 만든 뒤, 0/1로 미방문/방문을 표시하면 인덱스로 접근하여 바로 방문 여부를 알 수 있음
  • 이를 위해, 입력 받을 때부터 알파벳을 아스키코드값-65 형태로 저장했음.
    • e.g., A -> ord(A)-65 = 0, B -> ord(B)-65 = 1, ...