본문 바로가기
  • 안녕하세요,,, 안녕히가세요,,,,
프로그램/코딩테스트

백준 1987 알파벳

by 차보루타 2022. 6. 13.

 

from collections import deque

dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)

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

move_board = [input() for _ in range(R)]
check = [[set() for _ in range(C)] for _ in range(R)]
ans = 0


deq = deque()
deq.append((0, 0, move_board[0][0]))

check[0][0].add(move_board[0][0])


def err(a, b):
    return 0 <= a < C and 0 <= b < R


while deq :
    y, x, s = deq.popleft()

    ans = max(ans, len(s))

    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]

        if err(xx, yy) and move_board[yy][xx] not in s :
            ss = s + move_board[yy][xx]
            
            if ss not in check[yy][xx] :
                check[yy][xx].add(ss)
                deq.append((yy, xx, ss))

print(ans)

 

BFS를 이용해 해결했다.

 

체크 배열을 통해 이미 탐색된 내용을 저장해두고, 이미 탐색된 곳은 탐색에서 제외시킨다.

 

나머지는 일반적인 BFS와 같다.

 

'프로그램 > 코딩테스트' 카테고리의 다른 글

백준 7562 나이트의 이동  (0) 2022.06.13
백준 1743 음식물 피하기  (0) 2022.06.13
백준 2178 미로 탐색  (0) 2022.06.13
백준 11724 연결 요소의 개수  (0) 2022.06.13
백준 1449 수리공 항승  (0) 2022.06.13

댓글