글 읽기 - [파이썬] 순열이용풀이

tkddnjs1234 4년 전 0

BFS가 아닌 순열을 이용하여 풀어보았습니다.

순열에 대한 부분은 코드에 주석으로 설명을 달아두었습니다.

문제는 채점 시 메모리 초과가 뜬다는 것인데

이유가 무엇일까요?

from itertools import permutations
import sys

M, N = map(int, sys.stdin.readline().split())
maze = [[]] * N
for i in range(N):
    line = sys.stdin.readline()
    maze[i] = line[:M]  # '\n'을 제거해주기위해

# 1과 0으로 이루어진 리스트, 1은 오른쪽 0은 아래쪽으로 가는 걸 나타냄
right_or_down = []
for _ in range(M-1):
    right_or_down.append(1)
for _ in range(N-1):
    right_or_down.append(0)

min_cost_path = M+N
for case in list(permutations(right_or_down)):
    # 시작 위치
    start = [0, 0]
    cnt = 0
    for i in case:
        if i == 1:
            start[1] += 1
        elif i == 0:
            start[0] += 1
        if maze[start[0]][start[1]] == '1':
            cnt += 1
    min_cost_path = min(min_cost_path, cnt)

print(min_cost_path)

djm03178 4년 전 1

최대 크기일 때 순열의 개수는 22750883079422934966181954039568885395604168260154104734000개나 됩니다. 이 많은 것을 permutations로 다 생성할 수 있을 리가 없습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[파이썬] 순열이용풀이_메모리초과

tkddnjs1234 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말