[백준] 1987번 :알파벳

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

1987번: 알파벳

해당 문제는 완전탐색 + 깊이우선탐색 + 백트래킹 문제로 해결 할 수 있다.

 

같은 알파벳을 지날 수 없는것이 백트래킹 조건이고 깊이우선탐색과 완전탐색으로 모든 경로를 다 방문해 보면서 갈 수 없는 경로를 백 트래킹 하면 된다.

 

R, C = map(int, input().split())

board = [input() for _ in range(R)]
max_count = 0

def dfs(i, j, count, visited):
    global max_count
    max_count = max(max_count, count)

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    for dx, dy in directions:
        nx, ny = i + dx, j + dy
        if 0 <= nx < R and 0 <= ny < C and board[nx][ny] not in visited:
            dfs(nx, ny, count + 1, visited + board[nx][ny])

dfs(0, 0, 1, board[0][0])
print(max_count)