[BOJ] 그림 교환 in Python

문제 풀러 가기!

일단 전 이거 틀린게 맞는거 같습니다. 맞았습니다! 라고 떴지만, 문제에서 유도한 제약사항을 간신히 통과했고 문제에서 요구한 코드를 작성하지 않았기 때문에 틀린게 맞는거 같습니다.

ㅠㅠ

여튼 제가 풀이한 코드는 다음과 같습니다. 원래라면 틀려야되기 때문에

코드 설명은 안하겠습니다 ㅜㅜ

내 코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
price = [list(input().strip()) for _ in range(n)]
state = 1
answer = 1
is_buy = [[[1 for _ in range(n)] for _ in range(n)] for _ in range(1 << (n+1))]


def bfs(state, p, now):
    global answer

    q = deque([(state, p, now, 1)])

    while q:
        state, p, now, cnt = q.popleft()

        if answer < cnt: answer = max(answer, cnt)

        for nxt in range(n):
            if state & (1 << nxt): continue
            if p > int(price[now][nxt]): continue
            if is_buy[state][now][nxt] >= cnt+1:
                continue

            is_buy[state][now][nxt] = cnt+1
            q.append((state | (1 << nxt), int(price[now][nxt]), nxt, cnt + 1))

bfs(1, 0, 0)
print(answer)

단순하게 그냥 bfs 돌렸는데.. 음.. 시간이 너무 오래걸렸습니다..ㅋㅋㅋㅋㅋ 아직도 많이 부족하네요 ㅜㅜ

몇몇분들은 bfs로 돌린것을 알고 있으나, 제 bfs는 너무 비효율적이네요..ㅋㅋ