알고리즘 스터디 - 백준 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)
Author And Source
이 문제에 관하여(알고리즘 스터디 - 백준 1987번 : 알파벳), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@guri_coding/알고리즘-스터디-백준-1987번-알파벳저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)