반응형
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 3151 | 1606 | 1146 | 51.645% |
문제
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.*;
import java.util.*;
public class p14620 {
static int[] dr = {1, 0, -1, 0};
static int[] dc = {0, 1, 0, -1};
static int n, min = Integer.MAX_VALUE;
static int[][] map;
static boolean[][] visit;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
map = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
visit = new boolean[n + 1][n + 1];
dfs(0, 0);
System.out.println(min);
}
static void dfs(int depth, int sum) {
if (depth == 3) {
min = Math.min(min, sum);
return;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (!isPossible(i, j)) continue;
int tmp = getSum(i, j);
settingVisit(i, j, true);
dfs(depth + 1, sum + tmp);
settingVisit(i, j, false);
}
}
}
static void settingVisit(int r, int c, boolean type) {
visit[r][c] = type;
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
visit[nr][nc] = type;
}
}
static int getSum(int r, int c) {
int sum = map[r][c];
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
sum += map[nr][nc];
}
return sum;
}
static boolean isPossible(int r, int c) {
if (visit[r][c]) return false;
for (int dir = 0; dir < 4; dir++) {
int nr = r + dr[dir];
int nc = c + dc[dir];
if (OOB(nr, nc)) return false;;
if (visit[nr][nc]) return false;
}
return true;
}
static boolean OOB(int r, int c) {
return r < 1 || r > n || c < 1 || c > n;
}
}
반응형
'알고리즘 > [ Baekjoon ]' 카테고리의 다른 글
[ BOJ ][JAVA][14719] 빗물 (0) | 2021.05.05 |
---|---|
[ BOJ ][JAVA][14712] 넴모넴모 (0) | 2021.05.05 |
[ BOJ ][JAVA][14501] 퇴사 (0) | 2021.05.05 |
[ BOJ ]][JAVA][14500] 테트로미노 (0) | 2021.05.05 |
[ BOJ ][JAVA][14467] 소가 길을 건너간 이유 1 (0) | 2021.05.05 |