[백준14620] / 꽃길 - 브루트포스, 백트래킹

 

헤헤... 백트래킹이 아직 부족한거 같아서 백트래킹 풀기!!!

 

백준14620

 

 

푼 날짜 : 2024.12.05

푼 문제 : [14620] / 꽃길

사용한 언어 : python

알고리즘 : 브루트포스, 백트래킹

 

 

접근방식 :

백트래킹을 통해 전수조사를 진행한다. 

이 때 범위 자체가 작게 들어오기 때문에 시간초과는 걱정하지 않아도 된다.

 

꽃을 3개 심을 때마다 각 비용을 카운트 해서 정답 값을 더 작은 값으로 업데이트 했다.

 

 

코드 :

import sys

DIR = 4
input = sys.stdin.readline

N = int(input())
graph = []
for _ in range(N):
    lst = list(map(int, input().split()))
    graph.append(lst)

visited = [[0 for _ in range(N)] for _ in range(N)]

# 4 방향 탐색을 위함
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

# min값을 찾기 위한 초기값
ans = float("INF")

def countCost():
    global ans
    
    now_cnt = 0
    for i in range(N):
        for j in range(N):
            if visited[i][j]:
                now_cnt += graph[i][j]
	
    # 작은 값으로 업데이트
    ans = min(ans, now_cnt)

def backtracking(check, pi):
	# 3개의 꽃을 심었을 때는 비용 확인
    if check == 3:
        countCost()
        return

    for i in range(pi, N):
        for j in range(N):
        	# 현재 위치가 방문된 위치라면 컨티뉴
            if visited[i][j]: continue
			
            # 현재위치 기준 4 방향 모두 범위 내, 미방문인지 확인하기 위함
            now = True
            for k in range(DIR):
                ny, nx = i+dy[k], j+dx[k]
                if 0<=ny<N and 0<=nx<N and not visited[ny][nx]:
                    continue
                else:
                    now = False # 조건에 맞지 않는 위치가 하나라도 있다면 False처리
                    break
            
            # 진행에 문제가 없다면
            if now:
            	# 방문처리
                visited[i][j] = 1
                for k in range(DIR):
                    ny, nx = i+dy[k], j+dx[k]
                    visited[ny][nx] = 1
                    
                backtracking(check+1, i)
                
                # 방문 취소 처리
                visited[i][j] = 0
                for k in range(DIR):
                    ny, nx = i+dy[k], j+dx[k]
                    visited[ny][nx] = 0

# 처음 값은 꽃을 심는 회수, 그 다음 값은, 범위 생각했을 때 인덱스 1부터 시작하기 위함
backtracking(0, 1)
print(ans)

 

 

헤헤 최근 코테에서 백트래킹 문제를 잘 못푼거 같아서 아쉬운 마음이 있었는데 이렇게 조금씩 연습하면 나중에는 수월하게 풀 수 있겠지!?!

오늘도 한 단계 성장했다! 뿌듯