백준1987: 알파벳

1987번: 알파벳 문제 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된... www.acmicpc.net 이 문제는 대표적인 그래프 탐색 문제입니다.

깊이 우선 탐색을 이용하면 PyPy3로는 통과지만 Python3로든 시간 초과가 나서 여러 방면으로 생각하느라 고민 좀 했던 문제입니다. 1. Problem Analysis 구해야하는 것은 (R, C) 크기의 알파벳이 적힌 보드판에서 (1, 1)에서 말을 움...

요청 처리 중입니다...

백준1987: 알파벳

등록된 다른 글