글 읽기 - [Python] 시간초과 도와주십시오.. 다시 풀어도 안 풀리네요 ㅜ

kdk124578 2년 전 0

시간을 가장 많이 잡아먹는 부분은 상어 루트 찾기인 거 같아서

해당 로직을 중복순열이랑 백트래킹 두 개로 다 해봤는데도 시간초과가 뜨네요..

아예 싹 다 갈아엎어야 하는 건가요.

# https://www.acmicpc.net/problem/23290

from itertools import product

M, S = map(int, input().split())
fish_map = [[[] for _ in range(4)] for _ in range(4)]    # 물고기 기록
egg_map = [[[] for _ in range(4)] for _ in range(4)]     # 복제 예정인 것들 기록
smell_map = [[[] for _ in range(4)] for _ in range(4)]    # 상어가 잡아먹고 남은 냄새 기록 기록

# Init
for _ in range(M):
    i, j, d = map(int, input().split())
    fish_map[i - 1][j - 1].append(d - 1)
shark_x, shark_y = map(int, input().split())
shark_x -= 1
shark_y -= 1

dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]
dsx = [-1, 0, 1, 0]
dsy = [0, -1, 0, 1]


def find_fish_and_add_smell():
    '''현재 Fish Map에 있는 물고기 위치 전부 리턴'''
    '''또한 냄새들의 카운터 증가'''
    result = []
    for i in range(4):
        for j in range(4):
            for k in range(len(smell_map[i][j])):
                smell_map[i][j][k] += 1
            for d in fish_map[i][j]:
                result.append([i, j, d])
    return result


def move_fish():
    '''조건에 따라 물고기 이동'''
    
    for x, y, d in find_fish_and_add_smell():
        # 자기 자리에 알 생성 (복제 예정인 것들 추가)
        egg_map[x][y].append(d)
        for _ in range(8):
            nx, ny = x + dx[d], y + dy[d]
            if not (0 <= nx < 4 and 0 <= ny < 4) or [nx, ny] == [shark_x, shark_y] or smell_map[nx][ny]:
                d = (d - 1) % 8
                continue

            fish_map[nx][ny].append(d)
            del fish_map[x][y][0]
            break


def move_shark():
    '''조건에 따라 상어 움직이기'''
    
    global shark_x, shark_y

    # 루트 찾기
    route = []
    sub_route = []
    eat_cnt = 0

    for direction in product(range(4), range(4), range(4)):        # 중복순열로 다 해보기
        visited = [[False] * 4 for _ in range(4)]
        x, y = shark_x, shark_y

        eat_cnt_in_this_direction = 0
        is_moved_three_direction = True

        for d in direction:
            nx, ny = x + dsx[d], y + dsy[d]
            if not (0 <= nx < 4 and 0 <= ny < 4):
                is_moved_three_direction = False
                break

            if not visited[nx][ny]:    # 이전에 방문했더라면 해당 자리 물고기는 없을 것
                eat_cnt_in_this_direction += len(fish_map[nx][ny])
                visited[nx][ny] = True
            x, y = nx, ny

        if eat_cnt_in_this_direction < eat_cnt or not is_moved_three_direction:
            continue

        if not sub_route:
            sub_route = direction
        if eat_cnt < eat_cnt_in_this_direction:
            eat_cnt = eat_cnt_in_this_direction
            route = direction

    if not route:
        route = sub_route

    # 먹으면서 이동하기
    for d in route:
        nx, ny = shark_x + dsx[d], shark_y + dsy[d]
        if fish_map[nx][ny]:
            smell_map[nx][ny].append(0)
            fish_map[nx][ny] = []
        shark_x, shark_y = nx, ny


def remove_and_copy():
    '''냄새 2턴 이상 지난 것들 제거 and 복제 예정인 것들을 Fish Map에 추가(복제)'''
    for i in range(4):
        for j in range(4):
            fish_map[i][j] += egg_map[i][j]
            egg_map[i][j] = []
            while smell_map[i][j] and smell_map[i][j][0] == 2:
                del smell_map[i][j][0]


for _ in range(S):
    move_fish()
    move_shark()
    remove_and_copy()

ans = 0
for i in range(4):
    for j in range(4):
        ans += len(fish_map[i][j])
print(ans)

pichulia 2년 전 1

시간을 가장 많이 잡아먹는 부분은 이부분이지 않을까 싶습니다.

del fish_map[x][y][0]

kdk124578 2년 전 0

감사합니다. 큐로 바꿔서 popleft()로 해결했습니다! ㅜㅜ

del이 시간복잡도가 N이었군요.. 인덱스 접근이라 1인줄 알았는데 많이 아쉽네요.

열심히 해야겠습니다.

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

문제

문제

출처

ICPC

[Python] 시간초과 도와주십시오.. 다시 풀어도 안 풀리네요 ㅜ

kdk124578 2년 전 0

pichulia 2년 전 1

kdk124578 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말