글 읽기 - 가지치기 질문입니다.

park3three 3년 전 0

185번째 줄에서 궁수를 배치할 수 있는 모든 경우의 수를 combination으로 불러와서 반복문을 돌리는 형식으로 했는데

15x15 매트릭스로 해보니 시간이 초과되네요...

모든 경우의 수를 찾는 부분에서 가지치기를 할 수 있는 방법이 있을까요?

import sys
sys.stdin = open('input_17135.txt', 'r')

from itertools import combinations
from copy import deepcopy

# 적 이동
def moving():
    global remain_enemies
    for i in range(N-1, -2, -1):
        for j in range(M-1, -2, -1):
            if new_puzzle[i][j] == 1:
                new_puzzle[i][j] = 0
                if new_puzzle[i+1][j] == 0:
                    new_puzzle[i+1][j] = 1
                # 성에 도착하면 남은 적 수 -1
                elif new_puzzle[i+1][j] == 2:
                    remain_enemies -= 1

# out of index
def is_safe(y, x):
    return -1 < y < N and -1 < x < M

# 거리 계산
def cal_dist(y1, x1, y2, x2):
    return abs(y1-y2) + abs(x1-x2)

# 세 명의 궁수로부터 BFS
def attack(y1, x1, y2, x2, y3, x3, dist):
    global kills, remain_enemies
    dy = [-1, -1, -1]
    dx = [-1, 0, 1]
    Q1 = [[y1, x1]]
    Q2 = [[y2, x2]]
    Q3 = [[y3, x3]]
    visited_1 = [[0] * M for _ in range(N)]
    visited_2 = [[0] * M for _ in range(N)]
    visited_3 = [[0] * M for _ in range(N)]
    
    # visited에 궁수 사거리 기록
    while Q1:
        new_Q = Q1.pop(0)
        for i in range(3):
            new_y1 = new_Q[0] + dy[i]
            new_x1 = new_Q[1] + dx[i]

            if is_safe(new_y1, new_x1) and [new_y1, new_x1] not in visited_1:
                if cal_dist(new_y1, new_x1, y1, x1) <= dist:
                    visited_1[new_y1][new_x1] = cal_dist(new_y1, new_x1, y1, x1)
                    Q1.append([new_y1, new_x1])

    while Q2:
        new_Q = Q2.pop(0)
        for i in range(3):
            new_y2 = new_Q[0] + dy[i]
            new_x2 = new_Q[1] + dx[i]

            if is_safe(new_y2, new_x2) and [new_y2, new_x2] not in visited_2:
                if cal_dist(new_y2, new_x2, y2, x2) <= dist:
                    visited_2[new_y2][new_x2] = cal_dist(new_y2, new_x2, y2, x2)
                    Q2.append([new_y2, new_x2])

    while Q3:
        new_Q = Q3.pop(0)
        for i in range(3):
            new_y3 = new_Q[0] + dy[i]
            new_x3 = new_Q[1] + dx[i]

            if is_safe(new_y3, new_x3) and [new_y3, new_x3] not in visited_3:
                if cal_dist(new_y3, new_x3, y3, x3) <= dist:
                    visited_3[new_y3][new_x3] = cal_dist(new_y3, new_x3, y3, x3)
                    Q3.append([new_y3, new_x3])
    
    # 공격 가능한 적 중 최소거리 계산
    closest_enemy_dist_1 = 999999999
    for i in range(N):
        for j in range(M):
            if visited_1[i][j] > 0 and new_puzzle[i][j] == 1:
                if visited_1[i][j] < closest_enemy_dist_1:
                    closest_enemy_dist_1 = visited_1[i][j]

    closest_enemy_dist_2 = 999999999
    for i in range(N):
        for j in range(M):
            if visited_2[i][j] > 0 and new_puzzle[i][j] == 1:
                if visited_2[i][j] < closest_enemy_dist_2:
                    closest_enemy_dist_2 = visited_2[i][j]

    closest_enemy_dist_3 = 999999999
    for i in range(N):
        for j in range(M):
            if visited_3[i][j] > 0 and new_puzzle[i][j] == 1:
                if visited_3[i][j] < closest_enemy_dist_3:
                    closest_enemy_dist_3 = visited_3[i][j]
    
    # 공격 가능한 모든 적들의 index 리스트
    kill_lst_1 = []
    for i in range(N):
        for j in range(M):
            if visited_1[i][j] == closest_enemy_dist_1 and new_puzzle[i][j] == 1:
                kill_lst_1.append([i, j])

    kill_lst_2 = []
    for i in range(N):
        for j in range(M):
            if visited_2[i][j] == closest_enemy_dist_2 and new_puzzle[i][j] == 1:
                kill_lst_2.append([i, j])

    kill_lst_3 = []
    for i in range(N):
        for j in range(M):
            if visited_3[i][j] == closest_enemy_dist_3 and new_puzzle[i][j] == 1:
                kill_lst_3.append([i, j])
    
    # 공격 가능한 최소거리의 적이 여러 명일 경우 가장 왼쪽의 적의 index 기록
    # 공격 가능한 최소거리의 적이 한 명일 경우 그대로
    if len(kill_lst_1) > 1:
        closest_left = 999999999
        for i in range(len(kill_lst_1)):
            if kill_lst_1[i][1] < closest_left:
                closest_left = kill_lst_1[i][1]
        for i in range(len(kill_lst_1)):
            if kill_lst_1[i][1] == closest_left:
                kill_lst_1 = kill_lst_1[i]
                break
    
    elif len(kill_lst_1) == 1:
        kill_lst_1 = kill_lst_1[0]
    else:
        pass

    if len(kill_lst_2) > 1:
        closest_left = 999999999
        for i in range(len(kill_lst_2)):
            if kill_lst_2[i][1] < closest_left:
                closest_left = kill_lst_2[i][1]
        for i in range(len(kill_lst_2)):
            if kill_lst_2[i][1] == closest_left:
                kill_lst_2 = kill_lst_2[i]
                break
    elif len(kill_lst_2) == 1:
        kill_lst_2 = kill_lst_2[0]
    else:
        pass

    if len(kill_lst_3) > 1:
        closest_left = 999999999
        for i in range(len(kill_lst_3)):
            if kill_lst_3[i][1] < closest_left:
                closest_left = kill_lst_3[i][1]
        for i in range(len(kill_lst_3)):
            if kill_lst_3[i][1] == closest_left:
                kill_lst_3 = kill_lst_3[i]
                break
    elif len(kill_lst_3) == 1:
        kill_lst_3 = kill_lst_3[0]
    else:
        pass
    
    # 세 명의 궁수가 공격하게 될 적들의 index 리스트
    kill_lst = list(set([tuple(kill_lst_1), tuple(kill_lst_2), tuple(kill_lst_3)]))

    # 궁수 공격. 적이 있으면 남은 적 수 -1, 킬 수 +1
    for i in range(len(kill_lst)):
        try:
            if new_puzzle[kill_lst[i][0]][kill_lst[i][1]] == 1:
                new_puzzle[kill_lst[i][0]][kill_lst[i][1]] = 0
                remain_enemies -= 1
                kills += 1
        except:
            pass

# 데이터 인풋
N, M, D = map(int, input().split())
puzzle = [list(map(int, input().split()))  for _ in range(N)]

# 성을 맨 아래 행 밑에 삽입
puzzle.append([2]*M)

# 궁수를 배치할 수 있는 모든 경우의 수
set_archers_lst = list(combinations(list(range(0, M)), 3))

# 모든 궁수 배치 경우의 수에 대한 반복문
max_kills = 0
for i in range(len(set_archers_lst)):
    # 라운드 갱신
    kills = 0
    set_archers = list(set_archers_lst[i])
    new_puzzle = deepcopy(puzzle)
    
    # 남은 적 수 갱신
    remain_enemies = 0
    for p in range(N):
        for q in range(M):
            if new_puzzle[p][q] == 1:
                remain_enemies += 1
    
    # 적이 남아있으면 공격과 이동을 계속 반복
    while remain_enemies > 0:
        attack(N, set_archers[0], N, set_archers[1], N, set_archers[2], D)
        moving()
    
    # 해당 상황에서의 킬 수가 더 높을 경우 갱신
    if kills > max_kills:
        max_kills = kills

print(max_kills)

dmswl022329 2년 전 0

오래된 답변이지만...

일단 궁수가 적을 찾는데 드는 시간은 최대로 잡으면 O(D^2) 입니다. (D <= 10)

궁수가 적을 찾고 잡는데 드는 시간은 O(1) 로 계산할 수 있구요

그럼 궁수를 배치하는 방법은?

궁수 3명이 다 같으므로 3자리만 찾아서 넣어주면 됩니다(중복없이!)

제일 간단한 방법은 3중 for문으로 모든 경우를 오름차순으로 찾는겁니다

각 궁수의 좌표를 (i, j, k) 라고 하면

0 <= i < j < k < M <= 15을 만족하는 (i, j, k)의 수는 아무리 많아도 1만을 넘지 않죠

그래서 그냥 3중 for문으로 중복없이 돌리면 됩니다.

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

문제

문제

출처

ICPC

가지치기 질문입니다.

park3three 3년 전 0

dmswl022329 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말