백준 14620 꽃길 파이썬

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

14620번: 꽃길

백트레킹을 알고 있으면 쉽게 풀 수 있는 문제였다.

아래는 코드와 코드설명을 적어놨다.

def ch(i,j,mit,d):
    cs=0#크기를 저장해줄 변수
    for k in range(5):
       nx=dx[k]+i
       ny=dy[k]+j
       if 0<=nx<n and 0<=ny<n and not vist[nx][ny]:
           cs+=1#꽃잎의 크기
           mit+=s[nx][ny]#화단의 가격
           d.append((nx,ny))#화단의 위치
    if cs!=5:#cs는 꽃잎의 크기이다. 꽃잎이 살아있으려면 크기가 5여야하기 때문에 
    		#5가 안 되면 화단 대여를 안 해도 됨
        return ([],0)#d배열을 []로 리턴해줘서 밑에 if문의 조건으로 씀
    else:
        for x,y in d:#꽃잎이 만들어 질 수 있으니 True로 바꿔줌.
            vist[x][y]=True
        return (d,mit)
    
def lose(d):#방문 배열의 True->False로 고쳐주는 함수
    for i,j in d:
        vist[i][j]=False

def back(t,c):
    global re
    if t==3:#3개 심었으니 화단 가격 갱신해줌.
        re= min(re,c)#re값 갱신
    else:
        if c<re:#이미 더해준 값이 최솟값보다 크면 탐색을 더이상 해줄 필요가 없다! (시간 줄이기 포인트)
        #++테스트해보니 없어도 상관없다 그래도 있으면 12ms정도 더 빠르다
            for i in range(n):
                for j in range(n):
                    if not vist[i][j]:#방문했던 곳이 아니라면
                        d ,mit= ch(i,j,0,[])#ch함수실행
                        if d!=[]:#꽃잎이 만들어 질 수 있으니 백트레킹 시작
                            back(t+1,c+mit)
                            lose(d)#다시 방문배열을 다시 False고쳐준다.

   
n=int(input())
s = [list(map(int,input().split())) for _ in range(n)]
vist = [[False]*n for _ in range(n)]
dx=[0,0,1,-1,0]#자신 + 상하좌우 탐색
dy=[1,-1,0,0,0]#자신 + 상하좌우 탐색
re=1000000000000#200*5*3보다 큰 수이면 된다.
back(0,0)
print(re)