글 읽기 - [파이썬, 7576] 시간초과의 이유가 궁금합니다

tak8439 4년 전 0

이 문제에서 어떤 이유로 시간초과가 나는지 궁금합니다.

pypy3으로 해도 안되는걸 보면, 비효율적인 부분이 있다는 건데,

이미 들린 칸은 다시 안들리게 visited를 만드는 방법으로는 역부족인거일까요?

어떤 부분이 비효율을 만들었는지 궁금합니다.

감사합니다.

def solve(tomatoes, n, m):
    way_x = [-1, 1, 0, 0]  # 좌 / 우 / 상 / 하 x값 변화
    way_y = [0, 0, -1, 1]  # 좌 / 우 / 상 / 하 y값 변화
    visited = [[False] * m for _ in range(n)]
    next_block = []
    end_judge = 1
    # 첫 시작점들은 1인 좌표들에 대해서 넣어야 한다.
    for i in range(0, n):
        for j in range(0, m):
            if tomatoes[i][j] == 1:
                next_block.append([i, j])
            elif tomatoes[i][j] == 0:
                end_judge = 0

    if end_judge == 1:  # 시작하자마자 끝
        return 0

    else:  # 이제 돌아줘야 함
        day_val = 0
        while next_block:  # 더 꺼낼게 없을 때 까지
            x, y = next_block.pop(0)  # 꺼낼 거의 첫번째 위치
            if not visited[x][y]:
                visited[x][y] = True
                day_val = tomatoes[x][y]  # 지금 까지 걸린일자

                for i in range(4):
                    # 일단 4 방향중 하나를 들어가자
                    new_x = x + way_x[i]
                    new_y = y + way_y[i]
                    # 영역이 넘어갔으면 Fail
                    if new_x < 0 or new_y < 0 or new_x >= n or new_y >= m:
                        continue

                    if not visited[new_x][new_y]:
                        new_day_val = tomatoes[new_x][new_y]

                        if new_day_val == -1:  # 벽은 돌지 않아요
                            continue

                        elif new_day_val == 0 or day_val + 1 < new_day_val:  # 역류방지구문
                            tomatoes[new_x][new_y] = day_val + 1  # 이게 실행된다는 건, 새로운 길이다.
                            next_block.append([new_x, new_y])  # val + 1이 같거나 크다는건 이미 체크한 칸

        # 안 된 칸이 있나 체크
        end_judge_t = 1
        for i in range(n):
            for j in range(m):
                if tomatoes[i][j] == 0:
                    end_judge_t = 0
                    break

        if end_judge_t == 0:
            return -1

        else:
            return (day_val-1)


def main():
    m, n = map(int, input().split())
    tomatoes = []
    for i in range(n):
        tomato = list(map(int, input().split()))
        tomatoes.append(tomato)

    print(solve(tomatoes, n, m))

if __name__ == "__main__":
    main()

tak8439 4년 전 0

list랑 queue의 pop에서의 시간 복잡도 차이가 있다는 것을 알게되었습니다...

queue로 바꿔서 해결해보도록 하겠습니다.

dlaud5379 4년 전 1

코드를 대충 읽어보니 DFS를 돌리고 계시는군요! 이 문제는 문제 특성상 BFS로 탐색하면 (역류 방지만 잘 하면) 방문했던 칸을 다시 방문하지 않기 때문에 훨씬 효율적입니다. 저도 혹시 몰라서 예전에 BFS로 제출했던 C 코드를 DFS로 고치고 제출했더니 시간 초과가 나왔습니다.

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

문제

문제

출처

ICPC

[파이썬, 7576] 시간초과의 이유가 궁금합니다

tak8439 4년 전 0

tak8439 4년 전 0

dlaud5379 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말