백준 14620번 <꽃길>

백준 알고리즘 14620번

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

14620번: 꽃길

---

14620번

입력으로 첫 줄에 화단의 한 변의 길이 N이 들어온다. 그 다음 N개의 줄에 걸쳐 화단의 지점당 가격이 주어진다.

 

출력으로는 꽃 3개를 피울 때 최소 비용을 출력한다.

 

꽃을 심을 때, 꽃잎이 겹치면 죽는다.

---

문제 해결

화단이 많이 크지 않기 때문에 브루트포스 알고리즘을 사용할 수 있다. 

 

3중 for문을 돌려서 3개의 위치에 꽃을 심을 수 있는지 확인하는 함수 checkMap을 사용하였다.

꽃이 필 수 없는 경우와 꽃이 죽은 경우에는 10000을 반환하고 그렇지 않은 경우에는 꽃이 핀 지점 당 가격을 모두 더한 값을 반환한다.

 

N*N을 range로 해서 for문을 돌려서 따로 좌표를 구하면 6중 for문이 아니라 3중 for문으로 문제를 해결할 수 있다.

---

코드

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

def checkMap(lst):
    dx = [0, 1, -1, 0, 0]
    dy = [0, 0, 0, 1, -1]
    coordinate = []
    sum = 0
    for n in lst:
        x = n // N
        y = n % N
        for i in range(5):
            newX = x + dx[i]
            newY = y + dy[i]
            if newX >= N or newY >= N or newX < 0 or newY < 0:
                return 10000
            sum += Map[newX][newY]
            coordinate.append((newX, newY))
    if len(set(coordinate)) != 15:
        return 10000
    return sum
ans = 10000
for i in range(N*N):
    for j in range(i, N*N):
        for k in range(j, N*N):
            ans = min(ans, checkMap([i, j, k]))
print(ans)

---

결과

ㅕ

---