[C++] 백준 14620 : 꽃길

문제

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

 

 

 

코드

#include <iostream>
using namespace std;

int n; // 화단의 한 변의 길이
int G[11][11];  // 화단 지점별 가격
int visited[11][11];
int dx[5] = {0, 0,1,0,-1};
int dy[5] = {0, 1,0,-1,0};
int flower_point[3];
int min_cost = 5000; // 큰 숫자로 초기화 


int isPossible(){
    int cost = 0;
    
    for(int i=0; i<3; i++){
        // 1차원 index -> 2차원 배열 index
        int x = flower_point[i]/n;
        int y = flower_point[i]%n;
        
        
        for(int j=0; j<5; j++){
            int nx = x + dx[j];
            int ny = y + dy[j];
            
            // 화단 크기를 초과한 경우, 종료 
            if(nx >=n || nx <0 || ny >=n || ny<0) return 5000;
            
            // 이미 꽃이 심겨 있는 경우, 종료
            if(visited[nx][ny]==1) return 5000;
            
            // 방문 표시(= 꽃을 심음)
            visited[nx][ny] = 1;
            
            // 현재 꽃 심은 위치의 비용을 더함.
            cost += G[nx][ny];
        }
    }
    
    return cost;
}


// 모든 꽃 위치 조합 함수
void combi(){
    int p = n*n; // 2차원 배열 -> 1차원 배열 크기
    for(int i=0; i<p; i<i++){
        flower_point[0] = i;
        for(int j=i+1; j<p; j++){
            flower_point[1] = j;
            for(int k = j+1; k<p; k++){
                flower_point[2] = k;
                
                // 꽃 심기
                int cost = isPossible();
                
                // 이번 조합에서 비용이 저렴한 경우, 최소 비용 갱신
                if( cost < min_cost){
                    min_cost = cost;
                }
                
                // visited 배열 초기화
                for(int x=0; x<n; x++){
                    for(int y=0; y<n; y++){
                        visited[x][y] = 0;
                    }
                }
                
            }
        }
    }
}

int main()
{
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j =0; j<n; j++){
            cin >> G[i][j];
        }
    }
    
    // 모든 조합으로 꽃 심기
    combi();
    
    if(min_cost == 5000) cout << -1 << endl;
    else cout << min_cost << endl;
    
    return 0;
}

 

 

풀이 방법

  화단의 꽃을 심을 수 있는 위치 3개에 대한 모든 조합을 구하고, 각 조합마다의 비용을 계산하여 최소 비용을 출력하는 문제이다.

 

  이 문제를 풀면서 가장 고민했던 부분이 있다면 3개의 위치 조합을 어떻게 생성할까였다. x,y 각각에 대해 조합을 구하는 건 꽤나 복잡하다고 생각하여 그냥 0 ~ n*n-1 까지의 숫자 중 3개를 선택하고, 선택한 숫자를 x,y index로 변환하기로 하였다.

2차원 배열을 좌측 상단부터 우측 하단까지 가로순으로 번호를 매긴다고 생각하면 된다.
이렇게 하면 2차원 배열 index를 1차원 배열 index로 생각할 수 있다. 
위 문제의 경우, 2차원 배열의 가로, 세로 크기가 모두 같기 때문에 
  - 2차원 x = (1차원 Index) / (가로 크기 = n)
  - 2차원 y = (1차원 Index) % (세로 크기 = n)

 

 그래서 (1,2,3) -> (1,2,4) -> (1,2,5) -> ... / (2,3,4) -> (2,3,5) -> ... / (3,4,5) -> (3,4,6) -> (3,4,7) -> ... 이런 식으로 모든 꽃 위치 조합을 생성하도록 구현하였고, 각 위치를 2차원 배열의 index로 변환하여 방문해주었다.

 

이후로는 평범하게 방문 표시를 해주고, 재방문한 경우 방문 종료시키고, 방문 표시 배열을 초기화하는 일반적인 완전 탐색을 구현하면 된다.

 

또 이 문제에서 최소 비용을 어떤 값으로 초기화할지는 굉장히 단순한 편이었는데, 씨앗 하나당 차지할 수 있는 칸의 개수는 5개이고 한 칸의 최대 비용은 200이다. 그럼 씨앗 하나가 가질 수 있는 최대 비용은 1000이고, 씨앗이 총 3개 있기 때문에 3000이다. 난 그냥 5000이라는 숫자로 초기해주었다. 3000 보다 큰 숫자이기만 하면 된다.