14620_꽃길

입력

첫 번째 줄에 정사각형 화단의 한 변의 길이가 주어짐
두 번째 줄부터 N+1번째 줄까지 각 픽셀 마다의 cost값이 주어짐

출력

3개의 꽃을 심을 수 있는 최소한의 cost를 출력

조건

• 최종 꽃 3 송이를 심어야함
• 꽃 1 송이를 심는데 5 픽셀(중심+상하좌우)이 요구됨
• 꽃이 화단을 넘어가면 안됨

풀이

최대 10x10인 경우이기 때문에 모든 경우의 수를 돌며 최소의 합을 구한다. => dfs를 이용한 풀이

1. 꽃이 화단을 넘어가면 안되기 때문에 가장 자리는 후보에서 제외하고 (1,1) ~ (N-1,N-1)에서의 중심+상하좌우의 cost 값을 계산하여 sum_map 생성
   

dx = [0, -1, 0, 1, 0]
dy = [0, 0, -1, 0, 1]

for y in range(1, N-1):
    for x in range(1, N-1):
        tmp = 0
        for idx in range(5): tmp += _map[y+dy[idx]][x+dx[idx]]
        sum_map[y][x] = tmp

2. • cnt == 3일 경우
     현재 ans와 cost를 비교하여 더 작은 값으로 ans를 update
   • cnt != 3일 경우
     현재 좌표의 중심+상하좌우가 visit가 False인지 확인 후 False인 경우 해당 좌표의 중심+상하좌우를 True로 update한 후 현재 y축과 cost값, cnt값을 인자로 dfs 호출

def dfs(start, cnt, cost):
    global visited, ans, dx, dy, N, sum_map

    if cnt == 3: ans = min(ans, cost)
    else:
        for y in range(start, N-1):
            for x in range(1, N-1):
                flag = True
                for idx in range(5):
                    if visited[y+dy[idx]][x+dx[idx]]:
                        flag = False
                        break
                if flag:
                    for idx in range(5): visited[y+dy[idx]][x+dx[idx]] = True

                    dfs(start, cnt+1, cost+sum_map[y][x])

                    for idx in range(5): visited[y+dy[idx]][x+dx[idx]] = False

전체 코드

꽃길