[백준 문제풀이] 얼렁뚱땅 14620 꽃길 풀이

https://www.acmicpc.net/problem/14620

14620번: 꽃길

 

문제가 마아악 어렵지는 않지만 silver2? 는 아닌거같은 ..

진짜 다풀었는데 .. 

리스트 복사를 제대로 못해서 계속 틀렸었다.

 

그냥 새로운리스트=어떤리스트 이렇게 하면

주소값도 같이 복사되어서 새로운리스트에서 뭘 바꾸면 어떤 리스트도 같이 바뀐다

 

아니 근데 그거 알아서 새로운리스트=list(어떤리스트) 

요런식으로 했는데, 이거 1차원 리스트일때는 잘 되는거 같은데 2차원 넘으면 잘 안되나 보다 ^^....

 

copy.deepcopy() 이거써서 하면 완전 주소값다르게 복사 잘 된다

 

하ㅏㅏㅏㅏ 나는 bfs로 풀었는데, 사람들 보니까 dfs로 많이 풀어떠라

bfs는 시간초과 뜨기가 쉽다 dfs 보다 ..

그래서 그런가 python으로 했을 때 시간초과 뜨고 pypy로 했을 때 성공 됐다

dfs 로 푸는거 함 해봐야하는데 copy때매 쓴 내 시간에 진이 빠져서 다음에 해보도록 하겠따 그럼 뿅

 

from collections import deque
import copy

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
small = 100000000
visited = [[0]*n for _ in range(n)]

def bfs(visit,count,sum_) :
    global small
    queue = deque()
    t_visited = copy.deepcopy(visit)
    queue.append([t_visited,count,sum_]) 

    while queue :
        new_visit, new_count, new_sum = queue.popleft()

        if small < new_sum :
            continue
        
        temp_count = new_count + 1
        for p in range(1,n-1) :
            for q in range(1,n-1) :
                temp_visit = copy.deepcopy(new_visit)
                if temp_visit[p][q] == 0 and temp_visit[p-1][q] == 0 and temp_visit[p+1][q] == 0 and temp_visit[p][q-1] == 0 and temp_visit[p][q+1] == 0 :
                    n_sum = arr[p][q] + arr[p-1][q] + arr[p][q-1] + arr[p+1][q] + arr[p][q+1]
                    temp_sum = n_sum + new_sum
                    if temp_sum <= small :
                        temp_visit[p][q] = 1
                        temp_visit[p-1][q] = 1
                        temp_visit[p][q+1] = 1
                        temp_visit[p+1][q] = 1
                        temp_visit[p][q-1] = 1
                        temp_count = new_count + 1

                        if temp_count == 3 :
                            if small > temp_sum :
                                small = temp_sum
                        else :
                            queue.append([temp_visit, temp_count, temp_sum])

                        


for i in range(1,n-1) :
    for j in range(1,n-1) :
        m_visited = copy.deepcopy(visited)
        m_visited[i][j] = 1
        m_visited[i-1][j] = 1
        m_visited[i][j-1] = 1
        m_visited[i+1][j] = 1
        m_visited[i][j+1] = 1

        check_sum = arr[i][j] + arr[i-1][j] + arr[i][j-1] + arr[i+1][j] + arr[i][j+1]
        bfs(m_visited,1,check_sum)

print(small)