문제
알고리즘
백트래킹으로 해결하는 문제이다. 꽃잎이 화단을 넘어간다면 꽃이 죽게되므로 씨앗을 심을수 있는 범위는 화단의 가장자리를 제외하고 계산하면 된다.
꽃을 3개를 심으면 재귀가 종료되도록 하고, 다른 경우는 화단의 가장자리를 제외한 경우를 모두 탐색하면서 씨앗을 심고 dx,dy를 통해 꽃잎을 검사하는데, 이때 방문했다( 해당 자리에 미리 심은 씨앗이 있거나 꽃잎이 있는 경우)면 break를 통해 dx,dy반복문을 종료한다. 이때 방문하지 않았다(해당 자리에 미리 심은 씨앗이 없거나 꽃잎이 없는 경우)면 cost를 더해주고 다시 재귀를 반복한다.
코드
import sys
input = sys.stdin.readline
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, 0, 1, -1]
dy = [0, 1, -1, 0, 0]
visited = [[False]*n for _ in range(n)]
ans = [1e9]
def recur(cnt, price):
if cnt == 3:
ans[0] = min(ans[0], price)
return
for i in range(1, n-1):
for j in range(1, n-1):
flag = False
temp_cost = 0
cells = []
for d in range(5):
nx = i + dx[d]
ny = j + dy[d]
if visited[nx][ny]:
flag = True
break
temp_cost += arr[nx][ny]
cells.append((nx, ny))
if not flag:
for x, y in cells:
visited[x][y] = True
recur(cnt+1, price + temp_cost)
for x, y in cells:
visited[x][y] = False
recur(0, 0)
print(ans[0])
'Koala - 19기 > 코딩테스트 심화 스터디' 카테고리의 다른 글
[백준/Python] #15686: 치킨 배달 (0) | 2025.07.13 |
---|---|
[백준/python] 1051번 : 숫자 정사각형 (0) | 2025.07.13 |
[백준/Python] 18111 : 마인크래프트 (0) | 2025.07.13 |
[백준/python] 16401 : 과자 나눠주기 (0) | 2025.07.07 |
[BOJ/C++] 3273번: 두 수의 합 (0) | 2025.07.06 |