BOJ 14620 - 꽃길

문제

백준 온라인 저지 - 14620번

풀이 과정

백트래킹 을 이용한 탐색 문제입니다.
총 3개의 씨앗을 심을 수 있으며 특정 씨앗을 심을 경우 문제에서 제시된 인접한 위치에는 씨앗을 심을 수 없습니다.

문제에서 십자 모양으로 꽃이 피기 때문에 (1, 1) 부터 시작해서 (N - 1, N - 1) 까지만
탐색을 수행하면 된다는 것을 알 수 있습니다.
각 격자의 칸들을 이용해서 가능한 모든 조합을 만들어보면 되는데
이때 해당 위치에 씨앗을 심을 수 있는지 판단하는 함수를 하나 정의해서 구현합니다.

탐색할 때 주의할 점은 다음 위치부터 탐색하기 위해 (x, y) 값을 재귀적으로 넘겨주는데,
이때 y 가 끝에 도달할 경우(N - 2) 다시 y 축 탐색 시작 지점을 0으로 초기화 시켜주어야 한다는 점입니다.

코드

import sys

N = int(input())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dx = [1, -1, 0, 0, 0]
dy = [0, 0, 1, -1, 0]


def acc_flower(visit):
    acc = 0
    for x in range(N):
        for y in range(N):
            if visit[x][y]:
                acc += board[x][y]

    return acc


def is_acceptable(visit, x, y):
    for i in range(5):
        nx, ny = x + dx[i], y + dy[i]
        if visit[nx][ny]:
            return False

    return True


def set_flower(visit, x, y, val):
    for i in range(5):
        nx, ny = x + dx[i], y + dy[i]
        visit[nx][ny] = val


def dfs(visit, x, y, seed):
    if not seed:
        acc = acc_flower(visit)
        return acc

    ret = sys.maxsize
    for nx in range(x, N - 1):
        for ny in range(y, N - 1):
            if is_acceptable(visit, nx, ny):
                set_flower(visit, nx, ny, 1)
                ret = min(ret, dfs(visit, nx, ny, seed - 1))
                set_flower(visit, nx, ny, 0)
            # y축이 끝에 도달하면 1로 초기화
            if ny == N - 2:
                y = 1

    return ret


def solution():
    answer = sys.maxsize

    for x in range(1, N - 1):
        for y in range(1, N - 1):
            visit = [[0] * N for _ in range(N)]
            set_flower(visit, x, y, 1)
            answer = min(answer, dfs(visit, x, y, 2))
            set_flower(visit, x, y, 0)

    return answer


print(solution())