[백준_1987] 알파벳 python

풀다가 정신병 걸릴뻔했다.

이유도 너무 어이가 없는 것이,

충분히 무시해도 될 만한,

함수리턴과, zip << 이녀석들이 진짜 엄청 아주 매우 작은 차이를 만들어,

스노우볼로 내 코드를 느리게 하고 있었다.

 

물론, 실제 코테였다면 무시해도 될 정도의 시간복잡도 차이지만,

한표차이로 갈리는 투표마냥 이렇게 짜증나는 상황을 만들 힘도 충분히 가지고 있다는 것을 알게 해 주었다.

# 입력
# r, c 입력
r, c = map(int, input().split())

# grid 설계, 입력
grid = []
for _ in range(r):
    grid.append(list(input()))

# 함수들

# dfs(x, y, cnt)
def dfs(x, y, cnt):

    # 전역변수선언
    global ans

    # ans 업데이트
    ans = max(ans, cnt)
    
    # dxs dys -> 상 하 좌 우 순서 상관 x
    dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]

    for i in range(4):
        # 다음 위치 예측
        nx, ny = x + dxs[i], y + dys[i]
        # 갈 수 있으면
        if 0 <= nx and nx < r and 0 <= ny and ny < c and not grid[nx][ny] in visited_alphabet:
            
            # 방문 알파벳 적어주고
            visited_alphabet.add(grid[nx][ny])
            # dfs 호출
            dfs(nx, ny, cnt + 1)
            
            # 방문알파벳 제거 -> 최대치가 아닐 수도 있으므로
            visited_alphabet.remove(grid[nx][ny])

# 설계
# visited_alphabet -> 방문한 알파벳을 기록해 줄 세트
visited_alphabet = set()

# 제출용 정답
ans = 0

# 방문한 알파벳 기록해주고
visited_alphabet.add(grid[0][0])
# dfs 돌리기
dfs(0,0,1)

# 출력
print(ans)

늘 만들어왔던, chek 함수와 in_range함수를 포기하고 코드를 더럽게 짤 수 밖에 만들었다.

 

그래도 이 문제에서 배울 점은,

백트랙킹을 이용해 왔던 길을 다시 돌아갈 방법을 생각해야 한다는 것이다.