문제
2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.
진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.
하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.
꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.
꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.
그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.
하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.
단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.
돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!
입력
입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.
이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.
출력
꽃을 심기 위한 최소 비용을 출력한다.
예제 입력 1
6
1 0 2 3 3 4
1 1 1 1 1 1
0 0 1 1 1 1
3 9 9 0 1 99
9 11 3 1 0 3
12 3 0 0 0 1예제 출력 1
12문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[][] moves={{0,1},{0,-1},{1,0},{-1,0}};
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N=Integer.parseInt(br.readLine());
int[][] garden=new int[N][N];
int result=Integer.MAX_VALUE;
for(int i=0;i<N;i++){
st=new StringTokenizer(br.readLine());
for(int j=0;j<N;j++){
garden[i][j]=Integer.parseInt(st.nextToken());
}
}
//3개의 꽃 위치 찾기
//화단밖으로 나가면 안되기 때문에 (1,1)~(N-2,N-2) 까지 탐색
for(int i=1;i<N-1;i++){
for(int j=1;j<N-1;j++){
for(int a=1;a<N-1;a++){
for(int b=1;b<N-1;b++){
for(int c=1;c<N-1;c++){
for(int d=1;d<N-1;d++){
if((i==a && j==b) || (a==c && b==d) || (i==c && j==d)) continue;
//꽃이 모두 닿이지 않는지 체크
if(canPlant(i,j,a,b,c,d)){
//꽃 심는 비용 계산
int tmp=planting(garden,i,j,a,b,c,d);
result=Math.min(result,tmp);
}
}
}
}
}
}
}
System.out.println(result);
}
private static boolean canPlant(int i, int j, int a, int b, int c, int d) {
//대각선
int[][] dir={{-1,-1},{-1,1},{1,-1},{1,1}};
for(int[] di:dir){
if(i+di[0]==a && j+di[1]==b) return false;
if(a+di[0]==c && b+di[1]==d) return false;
if(c+di[0]==i && d+di[1]==j) return false;
}
//위아래 2칸차이,좌우 2칸차이
int[][] updown={{-1,0},{1,0},{0,-1},{0,1}};
for(int[] ud:updown){
for(int x=1;x<3;x++){
if(i+ud[0]*x==a && j+ud[1]*x==b) return false;
if(a+ud[0]*x==c && b+ud[1]*x==d) return false;
if(c+ud[0]*x==i && d+ud[1]*x==j) return false;
}
}
return true;
}
private static int planting(int[][] garden,int i, int j, int a, int b, int c, int d) {
int money=garden[i][j]+garden[a][b]+garden[c][d];
for(int[] m:moves){
money+=garden[i+m[0]][j+m[1]];
money+=garden[a+m[0]][b+m[1]];
money+=garden[c+m[0]][d+m[1]];
}
return money;
}
}꽃 3개를 이용하여 겹치지 않게 개화시키는데 필요한 비용을 계산하는 문제다.
꽃 3개라고 정해져있기 때문에 쉽게 구현이 가능했는데 조합을 이용해서 꽃의 위치를 구하려다가 그냥 for문을 중첩해서 완전탐색으로 구하기로 했다.
꽃을 개화시키는데 필요한 조건으로 꽃잎이 겹치면 안된다는 것이다.
꽃잎이 겹치는 경우는 다음과 같다.
- 꽃이 대각선으로 인접한 경우
- 상하좌우 2칸 이내로 위치한 경우
main
//3개의 꽃 위치 찾기
//화단밖으로 나가면 안되기 때문에 (1,1)~(N-2,N-2) 까지 탐색
for(int i=1;i<N-1;i++){
for(int j=1;j<N-1;j++){
for(int a=1;a<N-1;a++){
for(int b=1;b<N-1;b++){
for(int c=1;c<N-1;c++){
for(int d=1;d<N-1;d++){
if((i==a && j==b) || (a==c && b==d) || (i==c && j==d)) continue;
//꽃이 모두 닿이지 않는지 체크
if(canPlant(i,j,a,b,c,d)){
//꽃 심는 비용 계산
int tmp=planting(garden,i,j,a,b,c,d);
result=Math.min(result,tmp);
}
}
}
}
}
}
}6중 for문을 이용하여 꽃 3개의 위치를 모두 탐색해준다.
또한 꽃들의 위치가 같지 않도록 좌표값이 같은 경우가 나오면 continue로 넘겨준다.
꽃잎이 겹치지 않는다면 비용계산을 해주고 최소값으로 갱신해준다.
꽃이 겹치는지 확인하기
private static boolean canPlant(int i, int j, int a, int b, int c, int d) {
//대각선
int[][] dir={{-1,-1},{-1,1},{1,-1},{1,1}};
for(int[] di:dir){
if(i+di[0]==a && j+di[1]==b) return false;
if(a+di[0]==c && b+di[1]==d) return false;
if(c+di[0]==i && d+di[1]==j) return false;
}
//위아래 2칸차이,좌우 2칸차이
int[][] updown={{-1,0},{1,0},{0,-1},{0,1}};
for(int[] ud:updown){
for(int x=1;x<3;x++){
if(i+ud[0]*x==a && j+ud[1]*x==b) return false;
if(a+ud[0]*x==c && b+ud[1]*x==d) return false;
if(c+ud[0]*x==i && d+ud[1]*x==j) return false;
}
}
return true;
}각 꽃들이 대각선에 위치해있는지, 2칸이내로 위치해있는지 배열 값을 이용하여 반복문을 돌리고 겹치지 않는다면 true를, 겹친다면 false를 반환해준다.
꽃을 심는데 필요한 비용
private static int planting(int[][] garden,int i, int j, int a, int b, int c, int d) {
int money=garden[i][j]+garden[a][b]+garden[c][d];
for(int[] m:moves){
money+=garden[i+m[0]][j+m[1]];
money+=garden[a+m[0]][b+m[1]];
money+=garden[c+m[0]][d+m[1]];
}
return money;
}각 꽃들의 위치의 비용들과 상하좌우로 뻗었을때 필요한 비용들을 모두 합쳐 반환해준다.
생각보다 간단한 로직으로 풀 수 있는 문제였다. 단순하게 생각하고 하나씩 처리하면 금방 문제를 풀 수 있었다.
