[ 백준 ] 1987번 : 알파벳 (BFS / 파이썬)

문제 )

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

1987번: 알파벳

 

[ 풀이 IDEA ]

1. BFS/DFS로 풀어야하는 문제!

2. 그러나, 단순히 풀면 시간에러가 난다.

💡 SET 이용해서 문제 해결!

▶ BFS의 경우, queue대신에 set을 사용 & set에 좌표/visited(지나온 알파벳)을 저장한다

 

- python code 

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

def solution(board):
    global max_cnt
    q = set([(0, 0, board[0][0])])
    while q:
        x, y, visited = q.pop()
        max_cnt = max(max_cnt, len(visited))
        # 상하좌우 탐색
        for k in range(4):
            nx, ny = x+dx[k], y+dy[k] 
            if (0<=nx<r) and (0<=ny<c) and (board[nx][ny] not in visited):
                q.add((nx, ny, board[nx][ny]+visited))



r, c = map(int, input().split())
board = [list(input()) for _ in range(r)]
max_cnt = 0

solution(board)
print(max_cnt)