[BOJ] #1987 - 알파벳

1987번: 알파벳

 

 

** 문제 유형

• 백트래킹

 

** 풀이

1. 말은 상, 하, 좌, 우 4가지 방향으로 이동할 수 있음
2. 지금까지 지나온 모든 칸에 적혀 있는 알파벳과 다른 알파벳이 적힌 칸으로 이동해야 함
3. 행의 길이(r)와 열의 길이(c)가 20 이하이므로, 백트래킹을 이용하여 모든 경우의 수 고려해야 함

 

# 이동 좌표 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    global result
    # 동일한 경우는 한 번만 계산하기 위하여 집합(Set) 자료형 사용
    q = set()
    q.add((x, y, array[x][y]))

    while q:
        x, y, step = q.pop()
        # 가장 긴 이동 거리를 저장
        result = max(result, len(step))

        # 네 방향 (상, 하, 좌, 우)으로 이동하는 경우를 각각 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 이동할 수 있는 위치이면서, 새로운 알파벳인 경우
            if (0 <= nx and nx < r and 0 <= ny and ny < c and
                array[nx][ny] not in step):
                q.add((nx, ny, step + array[nx][ny])) # 경로를 문자열로 표현 ex) "CAD"

# 전체 보드 데이터를 입력 받음
r, c = map(int, input().split())
array = []
for _ in range(r):
    array.append(input())

# 백트래킹 수행 결과를 출력
result = 0
bfs(0, 0)
print(result)