백준_14620_꽃길

🗨️ Comment

• mat에서 3개의 지점을 뽑아야 한다 → 2차원리스트에서 조합을 이용해서 뽑기
  
• 조합에 사용할 리스트 만들기
  • candidates = [(r, c) for r in range(1, N-1) for c in range(1, N-1)]
  • row_col = list(product(list(range(1, N-1)), *repeat*=2))
• 만들어진 case에 대해서 4방향 탐색을 진행한다
  • 진행하면서 한 번이라도 이미 방문한 위치일 경우, 바로 return
  • 탐색과정에서 해당 case에 드는 평당 비용을 누적한다
  • 겹치지 않는 경우, 누적된 비용으로 min값을 갱신
• 전역변수로 만들어둔 min값을 처음에 1000으로 작게 선언했다가 틀렸다 → 최솟값은 맥시멈으로 설정하자..! 경계값으로 설정할거면 확실하게 계산하고 설정하자

⏰ 시간복잡도

• N의 최대값이 10이지만, 4개의 모서리 영역은 무조건 꽃이 죽으므로 제외 → 9*9_C_3 → 85320
  
• 각 case에 3개의 원소 → 원소마다 4번의 4방향 탐색 ⇒ 3*4
• 85320 * 12 ⇒ 1,023,840

⇒ 약 100만번으로 가능

---

📝 풀기 전 메모

# 2초 / 256MB
# 4:35 ~ 5:30
# 씨앗이 3개 -> 세개 꽃 모두 1년후 만개

# NxN
# 세개 모두 피면서 & 가장 싼 가격
# 대여가격 : 꽃 하나당 -> 5칸(평)

🥳 정답코드

from itertools import product, combinations
import sys
input = sys.stdin.readline

# N : 6이상 10이하 
N = int(input())
# 화단 지점당 가격
mat = [list(map(int, input().split())) for _ in range(N)]

# Solution 
# mat에서 3지점 고르기 => 중복조합으로, 행/열 뽑기 
row_col = list(product(list(range(1, N-1)), repeat=2))

# 꽃잎 4방향
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

min_price = 999999999

def check(case):
    """ 
    인자로 받은 case리스트 원소에 대해서 4방향 검사 -> 겹치는 영역이 있는지 확인한다
    case[i] : (r, c)
    """
    global min_price

    visited = [[0] * N for _ in range(N)]
    tmp_price = 0
    # case : 1, 2, 3돌면서 visited
    for r, c in case:
        # print(r, c)
        visited[r][c]= 1
        tmp_price += mat[r][c] 

        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]  

            # 방문체크
            if visited[nr][nc] == 0:
                visited[nr][nc] = 1
                tmp_price += mat[nr][nc]
            # 이미 방문되어있으면, 겹치는 경우 -> return 
            else:
                return 
    # return 되지 않았으면, 안 겹치는 경우 # 비용 갱신하기
    min_price = min(min_price, tmp_price)

for case in combinations(row_col, 3):
    # 해당 case에 대해 확인하기
    check(case)

# Output : 꽃을 심기 위해 필요한 최소비용
print(min_price)