[백준] 1987번 - 알파벳 (파이썬)

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

# 알파벳
import sys
input = sys.stdin.readline
R, C = map(int, input().split())
arr = []
for _ in range(R):
    arr.append(list(input().strip()))
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
result = 0


def move():
    global result
    q = set([(0, 0, arr[0][0])])
    while q:
        x, y, hist = q.pop()
        result = max(result, len(hist))
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < R and 0 <= ny < C:
                if arr[nx][ny] not in hist:
                    q.add((nx, ny, hist+arr[nx][ny]))


move()
print(result)

 

BFS

1. q에 초기값을 넣고 q가 빌 때까지

  - 상하좌우를 확인해서 hist문자열에 해당 arr의 값이 없다면 q에 append(기존 문자열에 추가해서)

2. result 출력

 

처음에 백트랙킹으로 풀다가 시간 초과가 나와서 결국 때려쳤다...

BFS로 풀 경우에는 not in / in 문법에서 일반적인 리스트로 풀이 시, 시간 복잡도가 O(N)이 나오지만

세트(Set)를 사용할 시, O(1)이 나온다. 이는 세트가 위치 테이블을 따로 가지고 있기 때문...

 

문제를 다 풀고 유형을 보니 백트랙킹이 맞았다 ㅂㄷㅂㄷ