[백준] 1987: 알파벳 (python 파이썬)

알파벳을 탐색할 때 고려해야할 조건은 다음과 같다.

• 다음에 탐색하는 인덱스가 배열 범위를 넘어가는가?
• 다음 알파벳을 이전에 만난적이 있는가?

위를 고려하여 DFS 방식으로 탐색하면 다음과 같이 구현할 수 있다.

import sys
input = sys.stdin.readline

def dfs(x, y, tmp):
    # 현재까지 탐색한 결과가 최대 이동 횟수라면 result에 저장한다.
    global result
    result = max(result, tmp)
    
    # 현재 위치에 해당하는 알파벳에 방문처리를 한다.
    index = ord(board[x][y])-ord("A")
    visited[index] = True
    
    # 모든 방향으로 이동하여 dfs 탐색을 수행한다.
    for i in range(4):
        next_x, next_y = x+dx[i], y+dy[i]
        if next_x < 0 or next_x >= row or next_y < 0 or next_y >= col:
            continue
        
        # 이동할 위치의 알파벳을 만난적이 없다면 해당 위치로 이동하여 dfs 탐색을 수행한다.
        next_index = ord(board[next_x][next_y])-ord("A")
        if not visited[next_index]:
            dfs(next_x, next_y, tmp+1)
                
    visited[index] = False
    
row, col = map(int, input().split())  # row, col: board판의 row, col을 의미
board = []  # board: board판의 정보를 담은 리스트
visited = [False for _ in range(26)]  # visited: 방문한 알파벳을 체크하는 리스트
result = 0  # result: 최대 이동 횟수

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

# 보드판 정보를 담아온다.
for _ in range(row):
    board.append(tuple(input().rstrip()))    

# dfs 탐색을 시작하고 결과를 출력한다.
dfs(0, 0, 1)
print(result)

위 방식은 python으로 제출시 시간 초과가 발생하고 pypy로 제출해야 정답으로 나온다. 아래 bfs 방식은 python으로 제출해도 잘 동작한다. 아마 set을 통해 탐색하는 경우를 줄여주기 때문인 듯 하다.

import sys
input = sys.stdin.readline

def bfs():
    global result
    
    # dfs와 달리 문자열로 만난 알파벳들을 확인한다.
    queue = set([(0, 0, board[0][0])])
    
    while queue:
        x, y, visited_alphas = queue.pop()
        result = max(result, len(visited_alphas))
        
        for i in range(4):
            next_x, next_y = x+dx[i], y+dy[i]
            if next_x < 0 or next_x >= row or next_y < 0 or next_y >= col:
                continue
            
            next_alpha = board[next_x][next_y]
            if next_alpha not in visited_alphas:
                queue.add((next_x, next_y, visited_alphas+next_alpha))
                
row, col = map(int, input().split())  # row, col: board판의 row, col을 의미
board = []  # board: board판의 정보를 담은 리스트
result = 0  # result: 최대 이동 횟수

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

for _ in range(row):
    board.append(tuple(input().rstrip()))    

bfs()
print(result)

 

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

1987번: 알파벳