[백준] 1987 알파벳 python(pypy), c

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

1987번: 알파벳

import sys; input = sys.stdin.readline
def backtrack(r, c):
    global answer
    # 1 길이 갱신
    answer = max(answer, len(alphabet))
    # 2 탐색
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        if 0 <= nr < N and 0 <= nc < M:
            if board[nr][nc] in alphabet:
                continue
            alphabet.add(board[nr][nc])
            backtrack(nr, nc)
            alphabet.remove(board[nr][nc])


N, M = map(int, input().split())
board = []
for _ in range(N):
    board.append(list(input()))

dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
alphabet = set()
alphabet.add(board[0][0])
answer = 1

backtrack(0, 0)
print(answer)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int N, M;
int answer = 0;
char board[20][20];
int alphabet[26] = { 0, };
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };

void backtrack(int r, int c, int cnt) {
    int ch_ord_ind, sum_val, nr, nc;
    
    ch_ord_ind = board[r][c] - 'A';
    if (alphabet[ch_ord_ind] == 1)
        return;

    alphabet[ch_ord_ind] = 1;

    if (answer < cnt) {
        answer = cnt;
    }

    for (int i = 0; i < 4; i++) {
        nr = r + dr[i];
        nc = c + dc[i];
        if (0 <= nr && nr < N && 0 <= nc && nc < M) {
            backtrack(nr, nc, cnt + 1);
        }
    }

    alphabet[ch_ord_ind] = 0;
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        char tmp[21];
        scanf("%s", &tmp);
        for (int j = 0; j < M; j++) {
            board[i][j] = tmp[j];
        }
    }
    backtrack(0, 0, 1);
    printf("%d", answer);
    return 0;
}

(0, 0)에서 시작하여 사방으로 탐색하면서 중복없이 만들수 있는 모든 조합을 찾는 백트래킹 문제이다.

python 에선 최대 길이를 set을 사용해서 확인했고 C에선 cnt를 통해 확인했다. 

백트래킹이면 가지치기를 해야하는데 어떤걸 가지치기 해야할지 모르겠다.

 

---

python에선 계속 시간초과가떠서 그냥 C로 진행했다...