[Python] 백준 1987 - 알파벳

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

1987번: 알파벳

 

많은 사람들이 DFS로 풀었는데 나는 BFS가 편해서 BFS로 풀었다.

 

처음에 deque로 접근하려 했다가 시간초과를 당했다.

 

자료구조 선택을 잘못했다. deque가 아닌 set으로 풀어야 통과가 됐다. 

deque로 풀게 되면 탐색 시간 복잡도가 O(n)이지만, set으로 풀면 O(1)이다. 

 

일반적인 BFS처럼 visited 배열을 따로 만들지 않고 단순 문자열로 방문 처리를 해주면 된다.

 

평소와 방문처리 방식이 달라지니 흥미롭게 문제를 풀 수 있었다.

# 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
# 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

n,m = map(int,input().split())

grid = [list(map(str,input())) for _ in range(n)]

dxs = [1,-1,0,0]
dys = [0,0,1,-1]


def bfs():
    q = set()
    q.add((0,0,grid[0][0]))

    maxCnt = 0

    while q:
        x,y,gone = q.pop()
        maxCnt = max(len(gone),maxCnt)

        for dx,dy in zip(dxs,dys):
            nx,ny = x+dx, y+dy

            if 0<=nx<n and 0<=ny<m and grid[nx][ny] not in gone:
                # gone: 지나갔던 알파벳을 문자열 형태로 쭉 나열
                q.add((nx,ny,gone+grid[nx][ny]))

    return maxCnt

print(bfs())