[알고리즘] 백준 14620 꽃길 / python

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

14620번: 꽃길

 

 

def func(lst):
    dx, dy = [0, -1, 0, 1, 0], [0, 0, -1, 0, 1]
    ck = []
    result = 0

    for flower in lst:
        x = flower // N
        y = flower % N

        if x==0 or x==N-1 or y==0 or y==N-1:
            return 10000

        for i in range(5):
            ck.append((x+dx[i], y+dy[i]))
            result += pot[x+dx[i]][y+dy[i]]
            
    if len(set(ck)) == 15:
        return result
    return 10000

N = int(input())
pot = [list(map(int, input().split())) for _ in range(N)]

price = 10000
for i in range(N*N):
    for j in range(N*N):
        for k in range(N*N):
            lst = [i, j, k]
            price = min(price, func(lst))
print(price)

 

처음엔 꽃의 위치를 x,y좌표로 생각하지 않고 6x6이라면 0,1,2,3...35를 좌표로 놓는다

꽃 3개의 위치를 삼중 반복문으로 돌린다

숫자로 표현된 좌표를 나누면 x좌표가, 나머지를 구하면 y좌표가 나온다

꽃이 피었을때, 5개의 좌표를 ck배열에 넣어서 set을 통해 중복이 있는지 확인

중복이 없다면 ck배열의 길이는 세개의 꽃 X 5평의 땅 = 15 이므로 result값을 return

중복이 있다면 다른 꽃잎과 닿게 될 경우 이므로 10000을 return 한다