알고리즘 스터디 - 백준 1987번 : 알파벳

문제 해석

R x C로 되어 있는 보드판 위에서 말이 지나갈 수 있는 최대의 칸 수를 구하기

• 각 칸마다 알파벳이 존재하는데 지금까지 지나온 알파벳과 다른 알파벳만 지나갈 수 있다
• R, C 둘다 1이상 20이하의 값으로 구성되어 있다

어떤 알고리즘을 써야할까?

• 일단, 상하좌우로 움직이는 방식에는 좌표를 이용한 BFS, DFS가 존재하고 있다.
• 기존 visited 배열이 True, False를 쓰는 것처럼 알파벳으로 방문 안했던 곳으로 새로 가는 방식으로 가면 된다.

알고리즘 코드

from collections import deque

R, C = map(int, input().split())
board = [list(input().strip()) for _ in range(R)]

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

answer = 1

def bfs(x, y):
    global answer
    q = deque()
    q.append((x, y, board[x][y]))

    while q:
        x_, y_, alpha_ = q.pop()

        for i in range(4):
            new_x = x_ + dx[i]
            new_y = y_ + dy[i]

            if ((0 <= new_x < R) and (0 <= new_y < C)):
                if board[new_x][new_y] not in alpha_:
                    q.append((new_x, new_y, alpha_ + board[new_x][new_y]))
                    answer = max(answer, len(alpha_) + 1)

bfs(0, 0)
print(answer)