๋ฌธ์
https://www.acmicpc.net/problem/17406
17406๋ฒ: ๋ฐฐ์ด ๋๋ฆฌ๊ธฐ 4
ํฌ๊ธฐ๊ฐ N×M ํฌ๊ธฐ์ธ ๋ฐฐ์ด A๊ฐ ์์๋, ๋ฐฐ์ด A์ ๊ฐ์ ๊ฐ ํ์ ์๋ ๋ชจ๋ ์์ ํฉ ์ค ์ต์๊ฐ์ ์๋ฏธํ๋ค. ๋ฐฐ์ด A๊ฐ ์๋์ ๊ฐ์ ๊ฒฝ์ฐ 1ํ์ ํฉ์ 6, 2ํ์ ํฉ์ 4, 3ํ์ ํฉ์ 15์ด๋ค. ๋ฐ๋ผ์, ๋ฐฐ์ด A์
www.acmicpc.net
๋ด ๋ฌธ์ ํ์ด
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int n, m, k;
static int[][] nums;
static int[][] cals;
static int min;
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};
static int[][] numsTmp;
static int cnt = 0;
public static int turn(int[][] res) {
numsTmp = new int[n][m];
for(int i = 0; i < n; i++) { // ๊น์ ๋ณต์ฌ
for(int j = 0; j < m; j++) {
numsTmp[i][j] = nums[i][j];
}
}
for(int[] now: res) {
int r = now[0];
int c = now[1];
int s = now[2];
int[] point1 = {r-s-1, c-s-1}; // ๊ฐ์ฅ ์ข์ธก ์๋จ ๊ผญ์ง์
int[] point2 = {r+s-1, c+s-1}; // ๊ฐ์ฅ ์ฐ์ธก ํ๋จ ๊ผญ์ง์
int turnNum = Math.min(point2[0]-point1[0]+1, point2[1]-point1[1]+1) / 2; // ํ์ ํ๋ ๋ ์ ๊ฐ์
for(int i = 0; i < turnNum; i++) { // ๊ฐ์ฅ ์ข์ธก ์๋จ ๊ผญ์ง์ ์ tmp๋ก ๋๊ณ ์๊ณ๋ฐฉํฅ ํ์
int x = point1[0] + i;
int y = point1[1] + i;
int startX = x;
int startY = y;
int tmp = numsTmp[x][y];
int dir = 0;
while(dir < 4) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if(nx < point1[0]+i || ny < point1[1]+i || nx > point2[0]-i || ny > point2[1]-i) {
dir++;
continue;
}
numsTmp[x][y] = numsTmp[nx][ny];
x = nx;
y = ny;
}
numsTmp[startX][startY+1] = tmp;
}
}
int minSum = Integer.MAX_VALUE;
for(int i = 0; i < n; i++) {
int minTmp = 0;
for(int j = 0; j < m; j++) {
minTmp += numsTmp[i][j];
}
minSum = Math.min(minSum, minTmp);
}
return minSum; // ํ์ฌ ์์ด์ ํ์ ์ฐ์ฐ์ ๋ง์น ๋ฐฐ์ด์ ๊ฐ ๋ฆฌํด
}
public static void permu(int[][] res, boolean[] visited, int depth) {
if(depth == k) {
min = Math.min(min, turn(res)); // ํ์ฌ ๋ง๋ ์์ด์ ํด๋นํ๋ ํ์ ์ฐ์ฐ ์งํ
return;
}
for(int i = 0; i < k; i++) {
if(!visited[i]) {
visited[i] = true;
res[depth] = cals[i];
permu(res, visited, depth+1);
visited[i] = false;
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(in.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
nums = new int[n][m];
cals = new int[k][3];
min = Integer.MAX_VALUE;
for(int i = 0; i < n; i++) {
st = new StringTokenizer(in.readLine());
for(int j = 0; j < m; j++) {
nums[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i = 0; i < k; i++) {
st = new StringTokenizer(in.readLine());
cals[i][0] = Integer.parseInt(st.nextToken());
cals[i][1] = Integer.parseInt(st.nextToken());
cals[i][2] = Integer.parseInt(st.nextToken());
}
permu(new int[k][3], new boolean[k], 0); // ์์ด ๋ง๋ค๋ฉด์, ์์ด ์์ฑํ ๋๋ง๋ค ํ์ ์ฐ์ฐ
System.out.println(min);
}
}
๐ ๊ตฌํ
์ ๋ ฅ๋๋ ํ์ ์ฐ์ฐ์ ๋ชจ๋ ๋ฐ์ ๋ค, ๊ทธ ์์์ ๋ํ ์์ด์ ๋ง๋ค๊ณ
ํ๋์ ์์ด์ด ์์ฑ๋ ๋๋ง๋ค ๊ทธ์ ํด๋นํ๋ ํ์ ์ฐ์ฐ์ ์งํํ๋ฉฐ ์ต์๊ฐ์ ๊ฐฑ์ ํ๋ค.
(๋ฐฐ์ด ๋๋ฆฌ๊ธฐ 2์์ ํ์ ์ฐ์ฐ์ ๊ดํ ์ ๋ฆฌ๋ฅผ ํด๋์์ -> https://seolhee2750.tistory.com/226)
โ๏ธ ๋ฐฐ์ด ๋๋ฆฌ๊ธฐ ์๋ฆฌ์ฆ ์ฝ๋ ์ฐธ๊ณ
๐ก ํผ๋๋ฐฑ
- ๋ณต์กํด๋ณด์์ง๋ง, ์ด์ ์ ๋ฐฐ์ด ๋๋ฆฌ๊ธฐ 1, 2, 3 ๋ฌธ์ ๋ฅผ ํ๋ฉด์
๋ฐฐ์ด ํ์ ์ ๊ดํด ๊ณต๋ถํ๊ธฐ ๋๋ฌธ์ ๊ฝค ์ฝ๊ฒ(?) ํ ์ ์์๋ค.
'2๏ธโฃ Java > Problem Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java Algorithm] ์จ๋ฐ๊ผญ์ง 2 BOJ #12851 (0) | 2022.08.16 |
---|---|
[Java Algorithm] ์ฌ์น์ฐ์ฐ ์ ํจ์ฑ ๊ฒ์ฌ SWEA #1233 (0) | 2022.08.11 |
[Java Algorithm] ๋ฐฐ์ด ๋๋ฆฌ๊ธฐ 2 BOJ #16927 (0) | 2022.08.10 |
[Java Algorithm] ํ ํ๋ก์ ํธ BOJ #9466 (0) | 2022.08.09 |
[Java Algorithm] ํธ๋ฆฌ BOJ #4803 (0) | 2022.08.09 |
๋๊ธ