글 읽기 - [파이썬, 시간초과] 브4가 골5 문제 3일동안 매달렸는데 모르겠어요..

heeyoungmy 3년 전 0

진짜 예쁘고 짧게 썼는데 왜 계속 시간초과가 뜰까요.. 도대체 왜...!!!!!!!!!!

N, M = map(int, input().split())

# 입력 행렬 생성
init_matrix = []
for _ in range(N):
    init_matrix.append(list(map(int, input().split())))

init_num_chick = 0
for row in init_matrix:
    init_num_chick += row.count(2)

# 치킨집을 몇개까지 줄여야 하나?
obj_num = min(M, init_num_chick)

# 집 좌표
house_cood = []

for row in range(N):
    for col in range(N):
        if init_matrix[row][col] == 1:
            house_cood.append([row,col])
            
# 치킨 좌표
chick_cood = []

for row in range(N):
    for col in range(N):
        if init_matrix[row][col] == 2:
            chick_cood.append([row,col])

# 치킨거리: 치킨 집 기준! 행마다 각 치킨 집과 모든 집들의 거리
temp = [0]*len(house_cood)
chick_distance = [temp[:] for i in range(len(chick_cood))]

for house_num in range(len(house_cood)):
    for chick_num in range(len(chick_cood)):
        chick_distance[chick_num][house_num] = abs(chick_cood[chick_num][0] - house_cood[house_num][0]) + abs(chick_cood[chick_num][1] - house_cood[house_num][1])
        
# 방문 여부 확인 함수
visited = [0]*len(chick_cood)

MIN = 1e9

# 재귀 함수
def omegamon(chick_index=0): 
    global MIN
    
    # 종료 조건
    if sum(visited) == obj_num:
        
        min_chick_distance_sum = 0
        for house_num in range(len(house_cood)):
            indi_mini = 1e3
            
            for i in range(len(visited)):
                if visited[i] == 1:
                    indi_mini = min(chick_distance[i][house_num], indi_mini)
            min_chick_distance_sum += indi_mini
        
        MIN = min(MIN, min_chick_distance_sum)
        return
    
    for i in range(chick_index, len(chick_cood)):
        # 방문 안 했으면 방문하기
        if visited[i] == 0:
            visited[i] = 1
            omegamon(chick_index+1)
            visited[i] = 0
        
omegamon(0)
print(MIN)

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

문제

문제

출처

ICPC

[파이썬, 시간초과] 브4가 골5 문제 3일동안 매달렸는데 모르겠어요..

heeyoungmy 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말