[백준][python]14620 꽃길

문제

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

소스코드1:  조합

import sys
import copy
from collections import deque
from itertools import combinations
input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    area = [list(map(int,input().split())) for _ in range(n)]
    combi = [(r,c) for r in range(1,n-1) for c in range(1,n-1)]
    res = 10**8

    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    def check(c):
        global res
        cost = 0
        visited = [[0] * n for _ in range(n)]
        for x,y in c:
            visited[x][y] = 1
            cost += area[x][y]
            for k in range(4):
                xx = x + dx[k]
                yy = y + dy[k]
                if not visited[xx][yy]:
                    cost += area[xx][yy]
                    visited[xx][yy] = 1
                else:
                    return
        res = min(res,cost)

    for c in combinations(combi,3):
        check(c)
    print(res)

설명

꽃점이 될 수 있는 위치를 조합을 이용해서 3개 뽑아준다.

위에서 뽑은 조합 경우의 수를 모드 체크해서 최소 값을 찾아본다

 

소스코드2: 백트래킹 + dfs

import sys
input = sys.stdin.readline

if __name__ == "__main__":
        n = int(input())
        res = 10**8
        total = 0
        arr = [list(map(int,input().split())) for _ in range(n)]
        visited = [[0] * n for _ in range(n)]
        dx = [0,1,-1,0,0]
        dy = [0,0,0,1,-1]
        def dfs(l):
            global res,total
            if l == 3:
                res = min(res,total)
                return

            for i in range(1,n-1):
                for j in range(1,n-1):
                    if not visited[i][j] and not visited[i-1][j] and not visited[i][j-1] and not visited[i+1][j] and not visited[i][j+1]: #상하좌우 1이 없는 경우 체크
                        for k in range(5): # (0,0) 나 자신도 포함해주기
                            x = i + dx[k]
                            y = j + dy[k]
                            visited[x][y] = 1
                            total += arr[x][y]
                        dfs(l+1)
                        for k in range(5): #백트래킹
                            x = i + dx[k]
                            y = j + dy[k]
                            visited[x][y] = 0
                            total -= arr[x][y]

        dfs(0)
        print(res)

설명

• 6≤N≤10 정도기 때문에 brute force로 모든 경우의 수를 다 체크해준다.
• 꽃이 필 수 있는지 상하좌우를 체크한 후 가능하다면  
  • 방문 체크
  • 비용 체크
• DFS로 다른 꽃을 탐색해준다.
• 백트래킹을 위해 방문체크를 해지하고 비용을 다시 원상복구 시켜준다.
• 3개 꽃을 다 탐색했으면 최소값을 구해준다.

중앙을 체크하고 dfs을 이용해서 꽃잎 하나하나를 해줬는데 시간이 너무 오래걸림

꽃 자체를 1단계로 보면 된다.