BOJ 1987 · 알파벳

알고리즘 분류 : DFS, 백트래킹  

N x M 사이즈의 보드에서 (0, 0) 부터 출발하여 최대한 많이 지날 수 있는 거리를 구하는 문제다. 단, 이동할 때 이미 지나쳤던 알파벳을 다시 지날 수 없다. DFS 기반에 백트래킹을 하면 된다.

• 방문 여부를 체크할 check 배열의 길이는 알파벳의 개수(26개) 만큼 선언한다.
• 상하좌우로 이동하면서, 방문하지 않은 알파벳이라면 true로 체크한다.
• 이동하면서, 이미 방문한 알파벳이라면 무시한다.
• DFS이므로, 가장 깊게 들어갔을 때가 정답이 된다.

---

C++ 소스코드

#include <cstdio>

int n, m, ans;
char a[20][20];
bool check[26];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void dfs(int x, int y, int z) {
    if (ans < z) ans = z;
    for (int i=0; i<4; i++) {
        int nx = x+dx[i], ny = y+dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        int c = a[nx][ny]-'A';
        if (check[c]) continue;
        check[c] = true;
        dfs(nx, ny, z+1);
        check[c] = false;
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) scanf("%s", a[i]);
    check[a[0][0]-'A'] = true;
    dfs(0, 0, 1);
    printf("%d\n", ans);
    return 0;
}

---

PyPy3 소스코드

n, m = map(int, input().split())
a = [list(input().strip()) for _ in range(n)]
check, ans = [False]*26, 0

def dfs(x, y, z):
    global ans
    ans = max(ans, z)
    for dx, dy in (-1, 0), (1, 0), (0, -1), (0, 1):
        nx, ny = x+dx, y+dy
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        c = ord(a[nx][ny])-ord('A')
        if not check[c]:
            check[c] = True
            dfs(nx, ny, z+1)
            check[c] = False

check[ord(a[0][0])-ord('A')] = True
dfs(0, 0, 1)
print(ans)

✓ Python 3로 제출하면 시간 초과가 나와서, PyPy3로 제출했다. 개선이 필요한 알고리즘이다.

---

참고

• 백준 온라인 저지 : BOJ 1987