글 읽기 - Python 시간초과 관련되어 질문드려봅니다.

ssnn2145 2년 전 0

모든 픽셀에대하여 이웃한 같은 값들을 가지는 픽셀들의 (세로,가로)의 크기의 최소값이 전체적으로 축소시킬수있는 행, 열이라 생각하여 알고리즘을

구현하였습니다... 허나 계속 시간초과가 일어나서 질문드립니다.. 방문하지않은것에대해서 방문하니 최대 O(N^2) 의 시간복잡도로 생각하는데

조건 N=10^3 이면 충분히 시간내에 정답처리될줄알았는데 계속 시간초과가 나네요...

혹시 도움을 주실 수 있으면 감사하겠습니다..

import sys
n,m = map(int,input().split())
a = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
v = [[False]*m for _ in range(n)]
dy = [-1,1,0,0]
dx = [0,0,-1,1]

def inside(y,x):
    return 0<=y<n and 0<=x<m

def go(y,x):
    v[y][x] = True
    q = [(y,x)]
    ref = a[y][x]
    na = [[False]*m for _ in range(n)]
    na[y][x] = True

    while q:
        y_,x_ = q.pop(0)

        for k in range(4):
            ny,nx = y_+dy[k],x_+dx[k]
            if not inside(ny,nx):continue
            if v[ny][nx]:continue
            if a[ny][nx]!=ref:continue
            v[ny][nx] = True
            na[ny][nx] = True
            q.append((ny,nx))
    rows = []
    cols = []
    for ii in range(n):
        if na[ii][x]:rows.append(ii)
    for jj in range(m):
        if na[y][jj]:cols.append(jj)
    return max(rows) - min(rows) +1,max(cols) - min(cols) +1

mr ,mc = 1000,1000

for i in range(n):
    for j in range(m):
        if not v[i][j]:
            row,col = go(i,j)
            mr = min(mr,row)
            mc = min(mc,col)

print(n//mr,m//mc)
for i in range(0,n,mr):
    string = ""
    for j in range(0,m,mc):
        string+=a[i][j]
    print(string)

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

문제

문제

출처

ICPC

Python 시간초과 관련되어 질문드려봅니다.

ssnn2145 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말