[백준] BFS + Depth, deque 대신 set / 알파벳

문제 개요

- 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 함

- 말이 최대한 몇 칸을 지날 수 있는지 (첫 번째 칸도 포함)

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

1987번: 알파벳

나의 코드

R, C = list(map(int, input().split()))
inputs = []
for _ in range(R):
    inputs.append(list(input()))

from collections import deque

def solution(R,C,inputs):
    max = 1
    # cand = deque([((0,0),inputs[0][0])])
    cand = set()
    cand.add(((0,0),inputs[0][0]))

    dx = [-1,0,0,1]
    dy = [0,-1,1,0]
    
    while cand:
        (x,y), a = cand.pop()
        for k in range(4):
            cx = x + dx[k]
            cy = y + dy[k]
            if cx<0 or cx>R-1 or cy<0 or cy>C-1:
                continue
            else:
                if inputs[cx][cy] not in a:
                    cand.add(((cx,cy), a+inputs[cx][cy]))
                    if len(a+inputs[cx][cy]) > max:
                        max = len(a+inputs[cx][cy])                 
                    
    return max

print(solution(R,C,inputs))

우여곡절

- 구현은 크게 어렵지 않았으나, 그놈의 효율성 문제... ㅎ

- BFS에 deque가 사용된다면 안 된다니! :D set 자료형을 사용해야 했다

why? 중복 이슈

deque의 시간복잡도는 O(1)이 맞음. 그러나 deque를 사용한 코드를 보면 중복값에 대해서도 모두 O(1)의 연산을 하니, 아무리 O(1)이지만 중복값이 수없이 많다면... 효율성 문제 발생. set 자료구조자체가 중복을 허용하지 않기때문에 훨씬 효율적으로 처리하며, 아마 deque에도 중복체크 넣으면 효율적으로 개선될 것.

=>같은 위치에 같은 문자열을 가진 상황을 중복해서 확인할 필요없으니, 같은 값은 같은 객체로 취급하는 집합 자료형을 사용

이라는데...... 이 문제에서 어떤 경우에 중복이 발생하는지 아직 이해하지 못했다.

그냥 visted에서 deque와 set 모두 구현해보고 시간이 더 빠른 걸 택한다는...분도 계셨다.

더 알아봐야겠다.

 

참고: https://www.acmicpc.net/board/view/81429

 

- 한번도 방문한 적 없은 알파벳만을 선택한다는 조건(a) 자체가 → visit한 원소는 아예 제외한다는 조건(b)을 포함한다

: 즉, a가 구현되면 b를 별도로 구현할 필요가 없다

: 즉, 방문한 알파벳에 대한 리스트(a)만 체크하면, 이미 방문한 원소에 대한 리스트(visited)를 따로 생성할 필요가 없다

 

- 참, 저기서 add할 때 a.append(inputs[cx][cy])로 하면 안 된다. for문 전체에 global하게 해당되는 a가 변형되기 때문이다. 슬라이싱 통해 temp로 복제하는 방법도 있지만, 그보다는 그냥 마지막에 cand에 add할 때 '+' 를 사용해주는 게 best!

 

새로 배운 것

1. 문자열(string)은 자기들끼리 덧셈 연산이 된다.

print('a'+'b') #ab

2. set 자료형

- append가 불가능한 대신 add로!

- pop을 할 경우 임의의 원소가 반환되므로, remove를 사용해야 한다 (나는 여기서... 대강 pop으로 때려맞혀서 이건 수정해야 한답)

https://blockdmask.tistory.com/451

[python] 파이썬 set (집합) 자료형 정리 및 예제

3. time 모듈로 코드 실행시간(시간복잡도) 측정

import time

#코드 하단에 추가
t0 = time.time()
print(time.time() - t0)

4. deque..

Deque(데크)는 double-ended queue 의 줄임말로, 앞과 뒤에서 즉, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조

https://excelsior-cjh.tistory.com/entry/collections-%EB%AA%A8%EB%93%88-deque

collections 모듈 - deque