[Python] 백준 '꽃길' 14620번 | 방향 벡터, 브루트 포스, DFS 알고리즘 문제

다른 문제 모음집

문제

2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.

진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.

하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.

꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.

꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.

그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.

하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.

단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.

돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

입력

입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.

이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.

출력

꽃을 심기 위한 최소 비용을 출력한다.

---

반응형

풀이

풀이 1 (2차원 배열을 1차원 배열로 생각해서 품)

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

dx, dy = [0, 1, -1, 0, 0], [0, 0, 0, 1, -1]  # 방향벡터 (현재 위치와 상하좌우 4방향)
anw = 10001  # 꽃 하나당 최고 비용 (200 * 5군데 = 1000), G의 범위가 0~200이라서 / 최대 비용인 1000을 넘는 임의의 수


# 비용 계산
def func(case: list) -> int:
    anw = 0
    flower = []  # 꽃의 위치 좌표를 쌓을 것임

    # case는 꽃의 1차원 배열 좌표를 가져옴
    for i in case:
        # 1차원 배열 좌표를 2차원 배열 좌표로 변경 (화단 밖으로 나가는 경우를 제외시키기 위해)
        x = i // N
        y = i % N
        if x == 0 or x == N - 1 or y == 0 or y == N - 1:
            return 10001  # 최대 비용 넘는 것으로 산정해서 min 함수에 걸리게 함
        # flower 리스트에 flower 위치 append / cost 계산
        for d in range(5):  # d = direction
            flower.append((x + dx[d], y + dy[d]))
            anw += G[x + dx[d]][y + dy[d]]

    # 꽃이 겹치는 경우 제외하기 위해 최대 비용 넘는 것으로 산정
    if len(set(flower)) != 15:
        return 10001

    return anw


# main
# 꽃의 위치를 2차원 배열에서 1차원 배열로 나타냄
for i in range(N ** 2):
    for j in range(i + 1, N ** 2):
        for k in range(j + 1, N ** 2):
            # 꽃의 위치가 1차원 배열로 나타나진 상태에서 func 함수로 비용을 구한 뒤에, min 함수로 최솟값을 구함
            anw = min(anw, func([i, j, k]))

print(anw)

• 꽃 3개의 경우를 i, j, k
• (0, 0) ~ (N, N) 2차원 배열을 0~ N*(N-1) 1차원 배열로 생각함. 이러면 꽃의 위치를 (1, 2), (0, 5) 같은 좌표로 나타내지 않고, 1차원 수인 3, 8과 같은 방법으로 나타낼 수 있음. 
• 1차원 배열로 나타내면 좋은 점: 꽃 3개의 위치를 모두 고려해볼 때, 위 코드처럼 보기 쉽게 사용할 수 있음. 예를 들어, (0, 1, 2), (0, 1, 3), (0, 1, 4), ..., (3, 4, 5), (3, 4, 6),..., (5, 8, 9)와 같이 좌표를 나타낼 수 있음. 화단을 넘거나 격자의 비용을 계산할 때는 1차원 배열을 2차원 배열로 나타내면 됨. (x좌표는 N으로 나눈 몫, y좌표는 N으로 나눈 나머지임)

풀이 2 (DFS, 브루트 포스)

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

dx, dy = [0, 1, -1, 0, 0], [0, 0, 0, 1, -1]  # 방향벡터 (현재 위치와 상하좌우 4방향)
visited = [[0] * N for _ in range(N)]
cnt = 0  # cnt = count, 3회가 최대 (꽃 3개이므로)
cost = 0  # 총 비용
anw = 10001  # 꽃 하나당 최고 비용 (200 * 5군데 = 1000), G의 범위가 0~200이라서 / 최대 비용인 1000을 넘는 임의의 수


# 격자에 꽃이 심어져 있으면, False 반환(=심지마라), 아니면 True 반환(=심어라)
def check(x, y):
    for d in range(5):
        x_ = x + dx[d]
        y_ = y + dy[d]
        if visited[x_][y_] == 1:
            return False
    return True


def dfs():
    global cnt, cost, anw

    if cnt == 3:
        anw = min(anw, cost)
        return

    for x in range(1, N - 1):
        for y in range(1, N - 1):
            if check(x, y):
                cnt += 1
                for d in range(5):
                    x_ = x + dx[d]
                    y_ = y + dy[d]
                    visited[x_][y_] = 1
                    cost += G[x_][y_]

                dfs()
                # 재귀하면서 visited와 cost, cnt가 갱신
                # cnt가 0 ,1, 2, 3이 되고, 최종적으로 if cnt == 3 구문에서 anw가 갱신된 뒤에
                # 남았던 이 for문의 일을 수행하게 됨. +1 했던 것을 -1 해주는 식
                cnt -= 1
                for d in range(5):
                    x_ = x + dx[d]
                    y_ = y + dy[d]
                    visited[x_][y_] = 0
                    cost -= G[x_][y_]


dfs()
print(anw)

• check 함수가 True이면, 본격적인 dfs 재귀 실행
• cnt(count) 변수는 꽃을 3개 심으므로 3이 최대. cnt ==3이면 dfs 반환
• 모서리 부분을 제외한 부분만 x,y 좌표를 둠. 따라서, range(1, N -1) 사용. (모서리 부분에 하면, 문제 조건에 위배)

출처

University > 인하대학교 > 2017 인하대학교 프로그래밍 경진대회(IUPC) I번

• 문제를 만든 사람: jason9319