글 읽기 - 코드 최적화

rlarudans134 2년 전 0

일단 제가 생각할 수 있는 선까지 최적화를 다 했다고 생각하는데, pypy3 처음 제출 때보다 더 개선된 속도를 보여 python3 로 제출 했더니 시간초과가 납니다... 혹시 고수님들이 코드 최적화 할 때 고려하는 부분들을 알려주실 수 있으신지요...

import sys
from collections import deque

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


def bfs(y, x, visit):
    visit[y][x] = True

    queue = deque()
    queue.append([y, x])

    # 여기서 추가해주면 중복을 굳이 생각할 필요가 없다. flag 와 get 리스트는 사실상 필요가 없었음
    # append 메소드 보다 그냥 누적합 처리를 해주면 더 빨라질까?
    result = graph[y][x]
    connect = 1
    location.append([y, x])

    while queue:
        y, x = queue.popleft()

        for v in range(4):
            nx = x + dx[v]
            ny = y + dy[v]

            if 0 <= nx < length and 0 <= ny < length and not visit[ny][nx]:
                if more <= abs(graph[y][x] - graph[ny][nx]) <= less:
                    result += graph[ny][nx]
                    # 연합 수 ++
                    connect += 1
                    location.append([ny, nx])

                    # 방문 처리를 꼭 해줘야함, 해당 정점은 이미 연합으로 판명 됬는데, 굳이 또 딴 곳에서 연합으로 중복 판명할 필요 x
                    queue.append([ny, nx])
                    visit[ny][nx] = True

    # 미리 추가하고 나서 더 이상 국가 추가가 없으니 이는 연합이 아님을 뜻한다.
    if connect > 1:
        for y, x in location:
            graph[y][x] = result // connect
        global migration
        migration += 1

    location.clear()


length, more, less = map(int, sys.stdin.readline().split())
location = deque()

migration = 0
cnt = 0

graph = [list(map(int, sys.stdin.readline().split())) for i in range(length)]

while True:
    check = [[False] * length for i in range(length)]

    for i in range(length):
        for j in range(length):
            if not check[i][j]:
                bfs(i, j, check)

    if migration < 1:
        print(cnt)
        break

    cnt += 1
    migration = 0

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

문제

문제

출처

ICPC

코드 최적화

rlarudans134 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말