[백준] 1987번: 알파벳

문제

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

1987번: 알파벳

 

풀이

DFS(깊이 우선 탐색), 백트래킹을 사용해 풀었습니다.

check 배열을 사용해 같은 알파벳이 적힌 칸을 두 번 지날 수 없도록 합니다.

ord 함수를 사용해 알파벳을 0~25의 값을 가지도록 합니다.

처음엔 딕셔너리를 사용해 알파벳을 체크해줬다. 그런데 계속 시간초과가 떠서 찾아보니 딕셔너리는 시간복잡도가 최소 O(1)에서 최대 O(n)까지 가능하다고 하여 리스트 인덱싱으로 바꿔주었다.

python을 제출할 때 Python3와 PyPy3 두 가지가 있는데 서로 장단점이 달라 상황에 맞게 사용해야 한다고 한다.

https://ralp0217.tistory.com/entry/Python3-%EC%99%80-PyPy3-%EC%B0%A8%EC%9D%B4

Python3 와 PyPy3 차이

 

코드

파이썬

import sys

input = sys.stdin.readline

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

R, C = map(int, input().split())
board = [list(input().rstrip()) for _ in range(R)]
check = [False] * 26
answer = 0


def DFS(x, y, L):
    global answer
    answer = max(answer, L)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < R and 0 <= ny < C:
            idx = ord(board[nx][ny]) - ord("A")
            if not check[idx]:
                check[idx] = True
                DFS(nx, ny, L + 1)
                check[idx] = False


check[ord(board[0][0]) - ord("A")] = True
DFS(0, 0, 1)
print(answer)