[백준 파이썬] #1987. 알파벳

풀기 전 생각해보기😮

• DFS로 풀이했다면 pypy3로 채점을 시도, BFS로 풀이했다면 python3로 채점할 수 있다고 한다.
  (자세한 이유까지는 모르겠다)

---

풀이🛫

# dfs 풀이는 pypy3로 제출해야 한다고 함: 자세한 이유는 모르겠다.. 
# 문제 채점 과정이 매우 오래 걸린다

# 정답
# U,R,D,L
dcol = [-1, 0, 1, 0]
drow = [0, 1, 0, -1]

def dfs(col, row):
    global level, max_level
    visited[col][row] = 1   # 방문 처리
    alpha_lst[ord(arr[col][row])-65] = 1    # 방문한 지점의 알파벳 처리
    level += 1  # 재귀가 반복될 때마다 깊이(level) 증가
    max_level = max(level, max_level)   ## max 처리를 이곳에서 했더니 오류가 발생하지 않음
    for v in range(4):
        ncol = col + dcol[v]
        nrow = row + drow[v]
        if 0<=ncol<R and 0<=nrow<C and visited[ncol][nrow] == 0 and alpha_lst[ord(arr[ncol][nrow])-65] == 0:
            dfs(ncol, nrow)		# dfs 탐색 진행

            # 재귀의 return 후 기록한 값을 초기화
            visited[ncol][nrow] = 0
            level -= 1
            alpha_lst[ord(arr[ncol][nrow])-65] = 0

R, C = map(int, input().split())    # R: 세로, C: 가로
arr = [list(input()) for _ in range(R)]
visited = [[0] * C for _ in range(R)]
alpha_lst = [0] * 26
level, max_level = 0, 0

dfs(0, 0)

if max_level == 0:
    max_level = 1

print(max_level)

 

핵심 정리🎁

• 알파벳의 값을 체크할 수 있도록 alpha_lst 리스트를 만들었다.
• 재귀가 진행될 때 아스키 코드값을 틍해서 alpha_lst를 확인하고, 탐색한 적이 없는 문자일 때 재귀를 진행했다.
• 재귀의 단계가 깊어질 때마다 level을 1씩 증가시켰다. level, max_level을 비교해서 max_level을 항상 level보다 같거나 큰값으로 유지시켰다.
• 재귀를 진행할 하면서 alpha_lst와 visited에 표시를 했고, 재귀가 끝났을 때 방문여부와 alpha_lst를 이전단계로 초기화, level을 -1해서 탐색할 수 있도록 한다.

 

링크💎

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

1987번: 알파벳

 

 

후기 😎

• max_level을 구하는 과정에서 위치를 잘못잡아 꽤나 고생했었다. max_level을 if문 안에넣어서 전개하다보니 조건문이 걸리지 않을 경우 max_level 값의 변경이 이뤄지지 않았었다. 정답과 관련된 변수를 if절에서 사용할 때는 주의해서 사용하도록 하자
• max_level은 level 값이 조정됨에 따라 결정되는 변수인 점을 기억하자. max_level의 갱신하는 코드를 level이 변할 때 최대한 가까운 곳에서 실행할 수 있도록 해야겠다