백준 14620번 꽃길(C++)

문제

14620번: 꽃길

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

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

정답 코드

코테 당시 통과 코드

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int N; //화단 한변의 길이
//0~N-1까지
//N~ 2N-1까지
//abs(b-a) == (N || N-1 || N+1)
int table[201][201];
int least_money = 2147483647;

int money_cnt(int x1,int y1){
	int cnt = 0;
	cnt +=table[y1][x1];
	cnt+= table[y1+1][x1];
	cnt+= table[y1-1][x1];
	cnt+= table[y1][x1-1];
	cnt+= table[y1][x1+1];
	return (cnt);
}

void make_three_flower(int a,int b,int c){
	int aMb = abs(b-a);
	int bMc = abs(b-c);
	int aMc = abs(a-c);
	if (aMb <=2 ||bMc <= 2 || aMc <=2)
		return ;
	if (a %N == 0 || a % N == N-1 || b % N == 0 || b % N == N-1 || c % N == 0 || c % N == N-1)
		return ;
	if ((N-1 <=bMc && bMc <= N+1 ) || (N-1 <=aMb && aMb <= N+1 ) || (N-1 <=aMc && aMc <= N+1 ))
		return ;
	if (aMb == 2*N || aMc == 2*N || bMc == 2*N)
		return ;
	int x1 = a%N;
	int y1 = a/N;
	int	x2 = b%N;
	int y2 = b/N;
	int x3 = c%N;
	int y3 = c/N;
	int cnt = 0;
	if (y1 == N-1 || y2 == N-1 || y3 == N-1 || x1 == N-1 || x2 == N-1 || x3 == N-1 || x1 == 0 || x2 == 0 || x3 == 0 || y1 == 0 || y2 == 0 || y3 == 0)
		return ;
	cnt+= money_cnt(x1,y1);
	cnt+= money_cnt(x2,y2);
	cnt+= money_cnt(x3,y3);
	if (cnt < least_money)
		least_money = cnt;
}
int main(){
	cin >> N;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			cin >> table[i][j];
		}
	}
	int max_N = N*N -1;
	for(int i=0;i<max_N;i++){
		for(int j=i+1;j<max_N;j++){
			for(int k=j+1;k< max_N;k++){
				make_three_flower(i,j,k);
			}
		}
	}
	cout << least_money<< "\n";	
}

최적화 코드

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int N; //화단 한변의 길이
//0~N-1까지
//N~ 2N-1까지
//abs(b-a) == (N || N-1 || N+1)
int table[201][201];
int least_money = 2147483647;

int money_cnt(int x1,int y1){
	int cnt = 0;
	cnt +=table[y1][x1];
	cnt+= table[y1+1][x1];
	cnt+= table[y1-1][x1];
	cnt+= table[y1][x1-1];
	cnt+= table[y1][x1+1];
	return (cnt);
}

void make_three_flower(int a,int b,int c){
	int x1 = a%N;
	int y1 = a/N;
	int	x2 = b%N;
	int y2 = b/N;
	int x3 = c%N;
	int y3 = c/N;
	if (abs(x1-x2) + abs(y1-y2) <=2 || abs(x1-x3) + abs(y1-y3) <=2|| abs(x2-x3) + abs(y2-y3) <=2)
		return ;
	int cnt = 0;
	if (y1 == N-1 || y2 == N-1 || y3 == N-1 || x1 == N-1 || x2 == N-1 || x3 == N-1 || x1 == 0 || x2 == 0 || x3 == 0 || y1 == 0 || y2 == 0 || y3 == 0)
		return ;
	cnt+= money_cnt(x1,y1);
	cnt+= money_cnt(x2,y2);
	cnt+= money_cnt(x3,y3);
	if (cnt < least_money)
		least_money = cnt;
}

int main(){
	cin >> N;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			cin >> table[i][j];
		}
	}
	int max_N = N*N -1;
	for(int i=0;i<max_N;i++){
		for(int j=i+1;j<max_N;j++){
			for(int k=j+1;k< max_N;k++){
				make_three_flower(i,j,k);
			}
		}
	}
	cout << least_money<< "\n";	
}

문제 풀이의 흐름

제약조건

일단 제약조건을 먼저 보면 화단의 한 변의 길이N이 최대 10이기 때문에 10*10으로 최대 100개의 점이 있고, 100개중에 3개를 선택하는 경우의 수를 넓게 잡아도 100*100*100번이므로 1000000번만 하면 된다.

주어진 시간은 2초이기 때문에 여유가 있음을 알 수 있다.

따라서 꽃을 놓을 수 있는 모든 위치를 탐색하는 것으로 문제를 해결하면 된다.

문제의 핵심 아이디어

여기서 나는 계산을 편하게 하기 위해서 + 코드를 조금 더 간단하게 하기 위해서 2차원 배열을 1차원으로 바꿔서 돌리도록 생각했다.

그래서 (0,0)에서 (0,N-1)까지를 일차원으로 0~N-1 로 설정하고 (1,0) ~ (1,N-1)을 N~ 2N-1로.. 이렇게 일차원으로 표현하였다.

	for(int i=0;i<max_N;i++){
		for(int j=i+1;j<max_N;j++){
			for(int k=j+1;k< max_N;k++){
				make_three_flower(i,j,k);
			}
		}
	}

결국 이 코드를 다 돌아서 정답을 구하는 방법을 사용했습니다.

make_three_flower 함수에서는 꽃들이 부딪히거나 끝에 닿는 꽃이 있다면 실행해서는 안됩니다.

끝에 꽃이 닿는 경우는

• x또는 Y좌표가 사각형 모서리에 닿아있는 경우

• 각 좌표가 둘 사이의 좌표의 차이가 2보다 같은 경우다.

그렇게 구현을 하기만 하면 끝이다.

주의 할 점

이 문제는 변수에 늪에 빠져서 헷갈려서 조건 하나를 잘못주면 한참 돌아갈 수 있는 문제기 때문에 천천히 하나씩 푸는 것이 중요하다고 생각한다.

반성 및 고찰

다음부터는 조금 더 깊게 생각하고 조건을 만들도록 하겠다.

Uploaded by N2T