https://www.acmicpc.net/problem/14620
๋ฌธ์ ๋ฅผ ํ์ดํ ๋ ์ฒ์์๋ ๊ฐ๊ฐ ์์น์ cost๋ฅผ ๊ตฌํ๊ณ cost๊ฐ ์์ ์์น๋ถํฐ ๊ฒน์น์ง ์๋ ์ ์์ ํฉ์ ๊ตฌํ๋ ์์ผ๋ก ํ์ด๋ฅผ ํ์๋ค. ํ์ง๋ง ์ด๋ฌํ ํ์ด๋ฒ์ ๊ฒฝ์ฐ์ ๋ฐ๋ผ ๊ฐ์ฅ cost๊ฐ ์ ์ ์์น๋ฅผ ํฌํจํ์ง ์๋ ์ต์๊ฐ์ด ๋์ฌ ์ ์๊ธฐ์ ์๋ชป๋ ํ์ด๋ฒ์ด์๋ค.
๋๋ฒ์งธ ํ์ด๋ฒ์ 3๊ฐ์ ๊ฝ์ ์์น์ ๋ํ์ฌ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ํ์ํ๋ ๋ฐฉ๋ฒ์ ์ฌ์ฉํ์ฌ ํ์ด๋ฅผ ํ์๋ค. ๊ฐ๊ฐ ํ์์ ํ๋ฉฐ ๊ฝ์ด ์์นํ ์ ์๋ ์์น์ด๊ฑฐ๋ ๊ฝ์ ์์น๊ฐ ๊ฒน์น๋ ๊ฒฝ์ฐ๋ ๋์ ์๋ฅผ returnํ๋ฉฐ ์ ์์ ์ธ ๊ฒฝ์ฐ์๋ ํด๋น cost๋ฅผ returnํ ์ต์๊ฐ์ ์ฐพ๋ ์์ผ๋ก ์ฝ๋ฉ์ ํ์๋๋ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์์๋ค.
๐ฅ๐ฅ ์๋ก ์์๊ฐ ๊ฒ ๐ฅ๐ฅ
2์ฐจ์ ๋ฐฐ์ด์ ๊ฒฝ์ฐ๋ 2์ค loop๊ฐ ์๋ ์๋์ ๊ฐ์ด N*N์ ํ์ ํ๋๋ง์ผ๋ก๋ ์ ์ฒด ํ์์ ํ ์ ์๋ค!!for (int i=0; i<(N*N); i++) { x = i/N; y= i%N; }
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Main {
static int[][]matrix;
static int N;
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
matrix = new int[N][N];
int answer = Integer.MAX_VALUE;
for (int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j=0; j<N; j++) {
matrix[i][j] = Integer.parseInt(st.nextToken());
}
}
// 3๊ฐ์ ๊ฝ ํ์
for (int i=0; i<(N*N); i++) {
for (int j=0; j<(N*N); j++) {
for (int k=0; k<(N*N); k++) {
ArrayList<Integer> list = new ArrayList<>();
list.add(i);
list.add(j);
list.add(k);
answer = Math.min(answer, findCost(list));
}
}
}
System.out.println(answer);
}
static int findCost(ArrayList<Integer> list) {
int[] dx = {0, -1, 1, 0, 0};
int[] dy = {0, 0, 0, -1, 1};
boolean[][] check = new boolean[N][N];
int result = 0;
for (int i: list) {
int x = i / N;
int y = i % N;
// ๊ฐ์ฅ ์๋ฆฌ์ ์์นํ๋ฉด ํ๋ฝ
if (x==0 || x==(N-1) || y==0 || y==(N-1)) {
return 10000;
}
for (int j=0; j<5; j++) {
if (!check[x+dx[j]][y+dy[j]]) {
check[x+dx[j]][y+dy[j]] = true;
result += matrix[x+dx[j]][y+dy[j]];
}
else return 10000;
}
}
return result;
}
}