[C++] 백준(BOJ) - 14620 : 꽃길

02 Nov 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 14620 : 꽃길(링크)

알고리즘

1. 브루트포스
2. 완전탐색

풀이

1. $100C3$ = 약 16만 정도의 시간 복잡도 - 완전 탐색 가능
2. 꽃을 심을 수 있는지 체크하는 알고리즘
3. 꽃을 심을 수있다면 setFlower 꽃을 심고, 가격 더하기
4. eraseFlower를 통해 방문처리 해제

코드

// BOJ-14620 : 꽃길
#include <bits/stdc++.h>
using namespace std;

const int INF = 2147000000;
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0,1,0,-1 };
int n, cost[14][14], flower[14][14], res = INF;

int setFlower(int y, int x)
{
    flower[y][x] = 1;
    int s = cost[y][x];
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        flower[ny][nx] = 1;
        s += cost[ny][nx];
    }
    return s;
}

void eraseFlower(int y, int x)
{
    flower[y][x] = 0;
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        flower[ny][nx] = 0; 
    }
    return;
}

bool check(int y, int x)
{
    if (flower[y][x]) return false;

    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || nx < 0 || ny >= n || nx >= n || flower[ny][nx]) return false;
    }
    return true;
}

void go(int cnt, int sum)
{
    if (cnt == 3)
    {
        res = min(res, sum);
        return;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (check(i, j))
            {
                go(cnt + 1, sum + setFlower(i, j));
                eraseFlower(i, j);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> cost[i][j];
        }
    }

    go(0, 0);

    cout << res << '\n';

    return 0;
}

평가

• 완전탐색의 기초 변형문제
  • 기저사례 꽃 3개를 다 심었을 때 최소 값인지 확인
  • 꽃을 심을 수 있는지 체크하는 함수가 먼저 필요
  • 방문처리와 동시에 sum 값을 더해 나가는 형태의 문제
  • 방문처리 해제를 하면서 배열 초기화