Search

BOJ 1987 알파벳

URL
태그
그래프 이론
그래프 탐색
깊이 우선 탐색
백트래킹

문제 설명

•
(1,1)(1, 1)부터 출발해서 나올 수 있는 알파벳의 최대 길이를 구하는 문제
◦
같은 알파벳이 적힌 칸을 두 번 지날 수는 없다.

예제 입력/출력

•
입력1
2 4 CAAB ADCB
Plain Text
복사
•
출력1
3
Plain Text
복사
더보기

제약 조건

•
1≤R,C≤201 ≤ R, C ≤ 20

문제 풀이

풀이1 브루트 포스
풀이2 그리디
풀이3 DP - O(R⋅C⋅226)O(R \cdot C \cdot 2^{26})

풀이 코드

deque를 이용한 백트레킹 (시간 초과)
set를 이용한 백트레킹 (python3 기준 통과)
list를 이용한 백트레킹 (pypy3 기준 통과)

알아두면 좋은 내용들

백트레킹(BackTracking) 문제인지 판별하는 법