글 읽기 - 코드의 시간초과 이유를 모르겠습니다.

badugijow 1년 전 0

안녕하세요 시간초과 질문드립니다. 코드 내에 네번쨰함수(bfs)를 풀어쓰면 시간초과가 해결되고 그대로 함수화해서 쓰면 시간초과로 틀리게되는데 그 이유가 뭔지 궁금합니다... 제가 볼 땐 시간복잡도는 똑같은 것 같은데 말이죠....ㅠㅠ 아래에 정답 코드도 같이 올려드립니다..

def get_new_xy(x,y,dir):

    if dir == 0:
        return x,y-1
    elif dir == 1:
        return x+1,y
    elif dir == 2:
        return x,y+1
    else:
        return x-1,y

def next_direction(dir):
    if dir%4 == 3:
        return 0
    else:
        return (dir%4)+1

def after_sand(x,y,dir,sand):
    global answer
    ds = [0.02,0.1,0.07,0.01,0.05,0.1,0.07,0.01,0.02]

    if dir==0:
        dx = [-2,-1,-1,-1,0,1,1,1,2]
        dy = [0,-1,0,1,-2,-1,0,1,0]
    elif dir == 1:
        dx = [0,1,0,-1,2,1,0,-1,0]
        dy = [-2,-1,-1,-1,0,1,1,1,2]
    elif dir == 2:
        dx = [2,1,1,1,0,-1,-1,-1,-2]
        dy = [0,1,0,-1,2,1,0,-1,0]
    else:
        dx = [0,-1,0,1,-2,-1,0,1,0]
        dy = [2,1,1,1,0,-1,-1,-1,-2]

    temp = 0
    for i in range(9):
        new_x,new_y = x+dx[i],y+dy[i]
        
        if 0<=new_x<N and 0<=new_y<N:
            # print(i,int(sand*ds[i]))
            arr[new_x][new_y] += int(sand*ds[i])
        else:
            answer += int(sand*ds[i])

        temp+=int(sand*ds[i])

    a,b = get_new_xy(x,y,dir)

    if 0<=a<N and 0<=b<N:
        plus_a = sand-temp
        arr[a][b] += plus_a
    else:
        plus_a = sand-temp
        answer+=plus_a

def bfs(dir):
    global roll_weight
    global start_x,start_y
    sand,x,y = 0,start_x,start_y
    
    for _ in range(dis):
        x,y = get_new_xy(x,y,dir)
        
        if arr[x][y]:
            sand = arr[x][y]
            after_sand(x,y,dir,sand)
            arr[x][y] = 0

        if x == 0 and y == 0:
            return dir,answer
    roll_weight += 1
    start_x,start_y = x,y
    new_dir = next_direction(dir)
    return new_dir,False



import sys
input = sys.stdin.readline

N = int(input())
answer = 0
arr = [list(map(int,input().split())) for _ in range(N)]

start_x,start_y = N//2,N//2 

dir = 0
dis = 1  # dis만큼 바람이 부는 방향으로 움직일 것이다
roll_weight = 0 # 짝수가 되면 dis가 +1 증가한다 

while 1:
    dir,flag = bfs(dir)
    if flag != False:
        print(flag)
        break
    if roll_weight%2 == 0:
        dis+=1
    

---------------------------------정답코드------------------------------------
def get_new_xy(x,y,dir):

    if dir == 0:
        return x,y-1
    elif dir == 1:
        return x+1,y
    elif dir == 2:
        return x,y+1
    else:
        return x-1,y

def next_direction(dir):
    if dir%4 == 3:
        return 0
    else:
        return (dir%4)+1

def after_sand(x,y,dir,sand):
    global answer
    ds = [0.02,0.1,0.07,0.01,0.05,0.1,0.07,0.01,0.02]

    if dir==0:
        dx = [-2,-1,-1,-1,0,1,1,1,2]
        dy = [0,-1,0,1,-2,-1,0,1,0]
    elif dir == 1:
        dx = [0,1,0,-1,2,1,0,-1,0]
        dy = [-2,-1,-1,-1,0,1,1,1,2]
    elif dir == 2:
        dx = [2,1,1,1,0,-1,-1,-1,-2]
        dy = [0,1,0,-1,2,1,0,-1,0]
    else:
        dx = [0,-1,0,1,-2,-1,0,1,0]
        dy = [2,1,1,1,0,-1,-1,-1,-2]

    temp = 0
    for i in range(9):
        new_x,new_y = x+dx[i],y+dy[i]
        
        if 0<=new_x<N and 0<=new_y<N:

            arr[new_x][new_y] += int(sand*ds[i])
        else:
            answer += int(sand*ds[i])

        temp+=int(sand*ds[i])

    a,b = get_new_xy(x,y,dir)

    if 0<=a<N and 0<=b<N:
        plus_a = sand-temp
        arr[a][b] += plus_a
    else:
        plus_a = sand-temp
        answer+=plus_a


import sys
input = sys.stdin.readline

N = int(input())
answer = 0
arr = [list(map(int,input().split())) for _ in range(N)]

start_x,start_y = N//2,N//2 

dir = 0
dis = 1  # dis만큼 바람이 부는 방향으로 움직일 것이다
roll_weight = 0 # 짝수가 되면 dis가 +1 증가한다 
flag = True

while flag:
    

    sand,x,y = 0,start_x,start_y
    
    for _ in range(dis):

        x,y = get_new_xy(x,y,dir)

        if arr[x][y]:
            sand = arr[x][y]
            after_sand(x,y,dir,sand)
            arr[x][y] = 0

        if x == 0 and y == 0:
            print(answer)
            flag = False
            break

    roll_weight += 1
    start_x,start_y = x,y

    dir = next_direction(dir)

    if roll_weight%2 == 0:
        dis+=1
    

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

문제

문제

출처

ICPC

코드의 시간초과 이유를 모르겠습니다.

badugijow 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말