[백준1987&파이썬] DFS와 백트래킹을 이용하여 조건에 맞는 값을 구하자

# 문제

백준 1987 알파벳 파이썬 풀이

1987번: 알파벳

# 코드

## 성공한 풀이

import copy
import sys
from collections import deque

R, C = map(int, sys.stdin.readline().split())

dirs = [
  (-1, 0), (0, 1), (1, 0), (0, -1)
  ]

# visit = [[True] * C for _ in range(R)] 방문처리가 필요하지 않음

board = list()
max_cnt = 0
for _ in range(R):
  line = list(sys.stdin.readline().strip())
  board.append(line)

# 방문했던 알파벳을 어떻게 관리할 것인가?
# 사용알파벳 관리
# print( ord('Z') - ord('A')) # 0 ~ 25
used = [False] * 26


def dfs(r, c, cnt):
  global max_cnt
  max_cnt = max(cnt, max_cnt)
  # print(f"({r},{c},{cnt})")

  for dir in dirs:
    next = (r + dir[0], c + dir[1])

    if 0 <= next[0] < R and 0 <= next[1] < C:
      if used[ord(board[next[0]][next[1]]) - ord('A')] == False:  # 사용하지 않았던 알파벳이라면
        used[ord(board[next[0]][next[1]]) - ord('A')] = True
        dfs(next[0], next[1], cnt + 1)
        used[ord(board[next[0]][next[1]]) - ord('A')] = False

used[ord(board[0][0]) - ord('A')] = True # 초기 시작점은 항상 사용됨
dfs(0, 0, 1)
print(max_cnt)

 

## 실패한 풀이 ( 시간 초과 )

import copy
import sys
from collections import deque

R, C = map(int, sys.stdin.readline().split())

dirs = [
  (-1, 0), (0, 1), (1, 0), (0, -1)
  ]

# visit = [[True] * C for _ in range(R)] 방문처리가 필요하지 않음

board = list()
max_cnt = 0
for _ in range(R):
  line = list(sys.stdin.readline().strip())
  board.append(line)


# ##### ------ 시간초과 풀이 ------ #####
# stk = deque()
# stk.append((0, 0, [],1))  # ( row, col, 방문했던 알파벳 )
#
# while len(stk) != 0 :
#   cur = stk.pop()
#   max_cnt = max(max_cnt,cur[3])
#
#   for dir in dirs :
#     next_list = copy.deepcopy(cur[2])
#     next_list.append(board[cur[0]][cur[1]])
#     next = ( cur[0] + dir[0], cur[1] + dir[1], next_list, cur[3] + 1 )
#
#     if 0 <= next[0] < R and 0<= next[1] < C : # 범위 체크
#         if board[next[0]][next[1]] not in next[2] : # 중복되는 알파벳이 없다면
#           stk.append(next) # 스택에 넣어주고
#
#
# print(max_cnt)
# ##### ------------------------ #####

 

# 풀이

## 이미 지났던 알파벳을 판단하는 방법

### 시간초과로 틀렸던 풀이

• bfs에서 프로시져방법을 이용해서 이전까지의 상태를 계속 이어오는 방법을 적용하여 DFS로 풀었다.
• 스택에 넣어주는 노드(단위)에서 현재를 뽑으면 3번째 인자에 담긴 리스트에 여기까지 오면서 밟았던 알파벳을 저장시켰다
• 그러나 deppcopy하는 과정과 거기 안에 해당 알파벳이 있는지 탐색하는 과정에서 시간이 많이 쓰여 시간초과가 난걸로 예상한다.

### 백트래킹과 사용한 알파벳을 GLOBAL에서 관리하기

• 백트래킹을 이용해 막혔을때 원래 상태로 되돌리는게 쉽게 가능하다. (아래 코드와 같이)

used[ord(board[next[0]][next[1]]) - ord('A')] = True
dfs(next[0], next[1], cnt + 1)
used[ord(board[next[0]][next[1]]) - ord('A')] = False

• 사용한 알파벳은 글로벌로 하고 한개만 사용해서 관리 할 수 있다. max(출력해야할 값)은 별도로 계속 최신화를 시킨다.
• 알파벳 대문자 'A' ~ 'Z' 까지 총 26개의 문자를 인덱싱하기 위해 아스키코드( ord ) 를 사용한다.

ord(board[next[0]][next[1]]) - ord('A')

• 이렇게 하면 'A'는 0 ... 'Z'는 25의 인덱스를 가지게 되고 해당 인덱스가 True/False인지에 따라서 다음 방문 여부를 결정한다.

## 방문처리는 필요하지 않았다. 

• 반복문으로 순서대로 돌고, 알파벳 사용 여부에 따라서 다음으로 이동이 가능한지를 판단한다.
• 이번에 그 방향으로 진출했다면 다음상황에 그 방향으로 어차피 진출 할 수 없다. (반복문에 의해서)

## 첫 시작점을 잊지 말자

• 다풀고 첫 시작점 방문처리를 안해서 오답이 나왔다. 

 

# 참고

• 백트래킹은 DFS도중 조건을 확인해 더이상 탐색하지 않아도 된다면 탐색하지 않는 것을 의미한다.
• 백트래킹은 일반적으로 재귀의 형태로 작성되고, 재귀가 종료되는 시점에서 다시 원래  상태로 복구 시키기 용이하고 깔끔하다.