[BOJ] 14620. 꽃길.py.cpp(전수조사)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

- 1년 후 꽃이 핌

- 꽃 씨앗이 세개밖에

- 다른 꽃잎과 닿게 될 경우 두 꽃 다 죽음

- 화단 밖으로 꽃잎이 나가도 죽음

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

- 최대 N은 10, N*N을 세 개의 꽃이 탐색해야하므로, (10*10)^3

- 1,000,000은 전수조사로 커버 가능

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

세 개의 꽃을 모든 곳에 심어보면서 최소비용을 구해보자.

다른 꽃과 닿거나 화단 밖으로 꽃잎이 나가면 꽃은 죽게되므로 이 경우는 pass

#. Python Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

N = int(input()) map = [list(map(int, input().split())) for _ in range(N)] dx, dy = [0, -1, 1, 0, 0], [0, 0, 0, -1, 1] mmax = 1000000000 res = mmax   def solve(lst):     res = 0     flower = []     for pos in lst:         x = pos // N         y = pos % N           if x == 0 or x == N-1 or y == 0 or y == N-1: return mmax           for c in range(5):             xx, yy = x + dx[c], y + dy[c]             flower.append((xx, yy))             res += map[xx][yy]       if len(set(flower)) == 15: return res     else: return mmax   for i in range(N*N):     for j in range(i+1, N * N):         for k in range(j+1, N * N):             res = min(res, solve([i, j, k]))   print(res) Colored by Color Scripter

cs

나는 아직도 한참 부족하다..

더 더 더 노력해야한다..

무튼 결국 힌트를 얻고 풀게되었다.

line 24~27) 세 개의 꽃씨를 모든 좌표에 심어보면서 전수조사를 수행한다.

line 27) result와 solve 함수 결과의 최솟값을 result에 다시 저장

line 7~22) 세 개의 꽃씨 좌표를 매개변수로 받는다.

line 10~19) 각 꽃씨의 좌표 기준으로 꽃을 피워본다.

line 11, 22) 각 좌표에 번호를 부여하여 (x, y) 좌표를 얻는 방법인데 참신한 방법인것 같다.

line 14) 화단의 테두리에 있을 경우 꽃이 죽게 되므로 바로 return 

     이 과정을 원래 꽃이 피었을 때 line 16 안에 넣었었는데 빼주면서 시간복잡도를 줄일 수 있었다.

line 16~19) 꽃이 피었을 때 꽃이 차지하는 좌표

line 18) 꽃이 차지하는 좌표가 겹치는지 확인하기 위해 flower list에 넣어준다.

line 19) 꽃이 차지하는 공간의 비용을 누적

line 21) 꽃이 차지하는 공간이 겹치지 않을 경우 누적액을 return

line 22) 꽃이 차지하는 공간이 겹칠 경우 max return

#. C++ Code

#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 2147000000
#define MIN -2147000000
 
int n, map[10][10], ch[10][10];
int dx[5] = { 0, -1, 1, 0, 0 }, dy[5] = { 0, 0, 0, -1, 1 };
 
int Solve(const int lst[])
{
    int i, j, sum = 0;
 
    for (i = 0; i < 3; i++)
    {
        int x = lst[i] / n;
        int y = lst[i] % n;
 
        if (x == 0 || x == n - 1 || y == 0 || y == n - 1)
            return MAX;
 
        for (j = 0; j < 5; j++)
        {
            int xx = x + dx[j];
            int yy = y + dy[j];
 
            if (ch[xx][yy] == 1)
                return MAX;
            else
                ch[xx][yy] = 1;
 
            sum += map[xx][yy];
        }
    }
 
    return sum;
}
 
int main(void)
{
    int i, j, k, a, b, res = MAX;
    
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
            scanf("%d", &map[i][j]);
    }
 
    for (i = 0; i < n*n; i++)
    {
        for (j = i+1; j < n*n; j++)
        {
            for (k = j+1; k < n*n; k++)
            {
                int lst[3] = { i, j, k };
                res = min(res, Solve(lst));
 
                for (a = 0; a < n; a++)
                {
                    for (b = 0; b < n; b++)
                        ch[a][b] = 0;
                }
            }
        }
    }
 
    printf("%d\n", res);
 
    return 0;
}