BAEKJOON 1697

19 Apr 2020

문제

입력

—–

나의 처음 코드

이 문제 비슷하게 카카오 코딩테스트인가 네이버인가 나왔던 문제이다. 처음 풀때는 시간초과가 났다. bfs문제의 경우에는 pop과 append를 어떻게 잘 활용해서 시간을 줄이는지가 관건인것 같다. 10,000이 넘어가는 순간 pop을 하면 1억번이 넘어가기 때문에 시간제한이 당연히 넘을 수 밖에 없을 것이다. 이 문제는 다른 여타의 문제와 같이 이동할 수 있는 경우의 수를 다 돌려서 동생 찾는 시간을 구하면 된다.

def solution(subin, sister):
    candidate_list = [[subin, 0]]
    check_list = [100000] * 100001
    if subin > sister:
        return subin - sister
    else:        
        while True:
            now_info = candidate_list.pop(0)
            if now_info[0] == sister:
                return now_info[1]
            #a-1
            if now_info[0] - 1 >= 0 and check_list[now_info[0]-1] > now_info[1] + 1:
                if now_info[0] - 1 == sister:
                    return now_info[1] + 1
                candidate_list.append([now_info[0]-1, now_info[1]+1])
                check_list[now_info[0]-1] = now_info[1] + 1    
            #a+1
            if now_info[0] + 1 <= 100000 and check_list[now_info[0] + 1] > now_info[1] + 1:
                if now_info[0] + 1 == sister:
                    return now_info[1] + 1
                candidate_list.append([now_info[0]+1, now_info[1]+1])
                check_list[now_info[0] + 1] = now_info[1] + 1
            #2a
            if now_info[0] * 2 <= 100000 and check_list[now_info[0] * 2] > now_info[1] + 1:
                if now_info[0] * 2 == sister:
                    return now_info[1] + 1
                candidate_list.append([now_info[0]*2, now_info[1]+1])
                check_list[now_info[0] * 2] = now_info[1] + 1
            
a, b = list(map(int, input().split()))
print(solution(a, b))           

결과는 시간초과. 흠 로직은 맞는데 시간초과가 난다… 어디서 문제일까 생각해보면 당연히 제일 아래 while문이 아니겠거니,,, 하고 다른 사람들의 코드를 보니 다들 import를 해서 deque로 푸는 것이 아닌가? 나는 not import 맨임으로 그렇게 풀지 않겠다. 자 그러면 문제의 부분을 어떻게 수정해서 풀것인가? pop을 하지 말고 append만 하는 코드를 만들어보자!

개선된 코드

import sys

M, N, H = list(map(int, sys.stdin.readline().split()))

tmt_map = []
dilic_tmt = []
tomato_cnt = 0

for stair in range(H):
    tmp = []
    for row in range(N):
        tmp_list = list(map(int, sys.stdin.readline().split()))
        tmp.append(tmp_list)
    tmt_map.append(tmp)

for s in range(H):
    for r in range(N):
        for c in range(M):
            if tmt_map[s][r][c] == 1:
                dilic_tmt.append((0, s, r, c))
                tomato_cnt += 1
            if tmt_map[s][r][c] == -1:
                tomato_cnt += 1
     
 
rl_side = [1, 0, -1, 0, 0, 0]
ud_side = [0, 1, 0, -1, 0, 0] #오른 아래 왼 위에
stair_updown = [0, 0, 0, 0, 1, -1] #위층 아래층
res = (N*M*H)

if tomato_cnt == res:
    print(0)
    
else:
    while dilic_tmt:
        if tomato_cnt == res:
            print(dilic_tmt[-1][0])
            break
        tmp = []
        #iteration으로 day별 익은 리스트를 넣는 것이다.
        for day, stair, row, col in dilic_tmt:
            for i in range(6):
                tmp_stair = stair + stair_updown[i]
                tmp_row = row + ud_side[i]
                tmp_col = col + rl_side[i]
                if tmp_stair >= 0 and tmp_stair < H and tmp_row >= 0 and tmp_col >= 0 and tmp_row < N and tmp_col < M and tmt_map[tmp_stair][tmp_row][tmp_col] == 0:
                    tmt_map[tmp_stair][tmp_row][tmp_col] = 1
                    tomato_cnt += 1
                    tmp.append((day+1, tmp_stair, tmp_row, tmp_col))
        dilic_tmt = tmp
                             
if tomato_cnt != res:
    print(-1)            

bfs의 경우에는 pop, push 시간을 줄이고, 또한 visited 리스트를 써서 방문한 노드를 재방문 하지 않게 하는것이 중요하다.