[백준] #1987 알파벳 -파이썬(python)

> 단계: 골드 4

> 문제링크: https://www.acmicpc.net/problem/1987

1987번: 알파벳

> 개념 참고: https://blog.naver.com/kks227/220786417910

백트래킹(Backtracking) (수정 2019-10-09)

 

 

문제를 풀 때 생각해야할 것

1. 이전 문제와 다르게 2차원!

2. 움직일 수 있는 곳이 상하좌우 4곳 (여느 길찾기 코딩 문제와 유사)

3. 알파벳 개수: 26개

 

풀이

*input에서 rstrip()을 해주는 이유: 안해주면 '\n'이 붙여있음

> 백준 pypy3으로 해야 시간초과가 안됩니다.<

import sys

def backtrack(nowrow,nowcol, dist):
    # nowrow, nowcol: 현재 말이 있는 위치 (0부터 시작)
    # dist: 현재 어디가지 왔는지

    global answer, alphabet, visited

    # 값이 더 큰 것으로 업데이트
    answer = max(answer, dist)
    # 간 곳 표시
    alphabet[ord(a[nowrow][nowcol])-ord("A")] = True
    visited[nowrow][nowcol] = True

    for i in range(4):
        nexrow = nowrow + dr[i]
        nexcol = nowcol + dc[i]
        
        if 0<=nexrow<r and 0<=nexcol<c and not visited[nexrow][nexcol] and not alphabet[ord(a[nexrow][nexcol])-ord("A")]:
            # 새로가려는 곳의 위치가 범위 내에 있고, 안지나간 알파벳인지 확인
            backtrack(nexrow, nexcol, dist+1)
        
        else:
            # 위의 조건에 해당이 안되면, 다음 후보로 넘어 감
            continue

    # 주변 갈 수 있는 노드 하나의 끝을 가면, 다시 안가본 곳부터 해야하니까 False로
    visited[nowrow][nowcol] = False
    alphabet[ord(a[nowrow][nowcol])-ord("A")] = False
            

input = sys.stdin.readline

# input 가져오기
r, c = map(int, input().split()) # row, column
a = [list(input().rstrip()) for i in range(r)] # 2차원 [[]]

# 필요한 것들
alphabet = [False]*26 # 알파벳 개수(지난 곳은 True로 체크)
visited = [[False]*c for _ in range(r)]
answer =0

# 이동방향
dr=[-1,1,0,0]
dc=[0,0,-1,1]
answer = 1 # 말이지나는 칸 수
backtrack(0,0,1)
print(answer)