[Algorithm] ๐ช๏ธ๋ฐฑ์ค 17144 ๋ฐฐ์ด ๋๋ฆฌ๊ธฐ4
0. ๋ฌธ์
ํฌ๊ธฐ๊ฐ NรM ํฌ๊ธฐ์ธ ๋ฐฐ์ด A๊ฐ ์์๋, ๋ฐฐ์ด A์ ๊ฐ์ ๊ฐ ํ์ ์๋ ๋ชจ๋ ์์ ํฉ ์ค ์ต์๊ฐ์ ์๋ฏธํ๋ค. ๋ฐฐ์ด A๊ฐ ์๋์ ๊ฐ์ ๊ฒฝ์ฐ 1ํ์ ํฉ์ 6, 2ํ์ ํฉ์ 4, 3ํ์ ํฉ์ 15์ด๋ค. ๋ฐ๋ผ์, ๋ฐฐ์ด A์ ๊ฐ์ 4์ด๋ค.
1 2 3
2 1 1
4 5 6
๋ฐฐ์ด์ ํ์ ์ฐ์ฐ์ ์ํํ ์ ์๋ค. ํ์ ์ฐ์ฐ์ ์ธ ์ ์ (r, c, s)๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , ๊ฐ์ฅ ์ผ์ชฝ ์ ์นธ์ด (r-s, c-s), ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ์๋ซ ์นธ์ด (r+s, c+s)์ธ ์ ์ฌ๊ฐํ์ ์๊ณ ๋ฐฉํฅ์ผ๋ก ํ ์นธ์ฉ ๋๋ฆฐ๋ค๋ ์๋ฏธ์ด๋ค. ๋ฐฐ์ด์ ์นธ (r, c)๋ rํ c์ด์ ์๋ฏธํ๋ค.
์๋ฅผ ๋ค์ด, ๋ฐฐ์ด A์ ํฌ๊ธฐ๊ฐ 6ร6์ด๊ณ , ํ์ ์ฐ์ฐ์ด (3, 4, 2)์ธ ๊ฒฝ์ฐ์๋ ์๋ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ํ์ ํ๊ฒ ๋๋ค.ํ์ ์ฐ์ฐ์ด ๋ ๊ฐ ์ด์์ด๋ฉด, ์ฐ์ฐ์ ์ํํ ์์์ ๋ฐ๋ผ ์ต์ข ๋ฐฐ์ด์ด ๋ค๋ฅด๋ค.
ํ์ ์ฐ์ฐ์ด ๋ ๊ฐ ์ด์์ด๋ฉด, ์ฐ์ฐ์ ์ํํ ์์์ ๋ฐ๋ผ ์ต์ข ๋ฐฐ์ด์ด ๋ค๋ฅด๋ค.
๋ค์์ ๋ฐฐ์ด A์ ํฌ๊ธฐ๊ฐ 5ร6์ด๊ณ , ํ์ ์ฐ์ฐ์ด (3, 4, 2), (4, 2, 1)์ธ ๊ฒฝ์ฐ์ ์์์ด๋ค.
๋ฐฐ์ด A (4, 2, 1) ์ฐ์ฐ ์ํ ํ (3, 4, 2) ์ฐ์ฐ ์ํ ํ
๋ฐฐ์ด A์ (3, 4, 2), (4, 2, 1) ์์๋ก ์ฐ์ฐ์ ์ํํ๋ฉด ๋ฐฐ์ด A์ ๊ฐ์ 12, (4, 2, 1), (3, 4, 2) ์์๋ก ์ฐ์ฐ์ ์ํํ๋ฉด 15 ์ด๋ค.
๋ฐฐ์ด A์ ์ฌ์ฉ ๊ฐ๋ฅํ ํ์ ์ฐ์ฐ์ด ์ฃผ์ด์ก์ ๋, ๋ฐฐ์ด A์ ๊ฐ์ ์ต์๊ฐ์ ๊ตฌํด๋ณด์. ํ์ ์ฐ์ฐ์ ๋ชจ๋ ํ ๋ฒ์ฉ ์ฌ์ฉํด์ผ ํ๋ฉฐ, ์์๋ ์์๋ก ์ ํด๋ ๋๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ๋ฐฐ์ด A์ ํฌ๊ธฐ N, M, ํ์ ์ฐ์ฐ์ ๊ฐ์ K๊ฐ ์ฃผ์ด์ง๋ค.
๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ๋ฐฐ์ด A์ ๋ค์ด์๋ ์ A[i][j]๊ฐ ์ฃผ์ด์ง๊ณ , ๋ค์ K๊ฐ์ ์ค์ ํ์ ์ฐ์ฐ์ ์ ๋ณด r, c, s๊ฐ ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
๋ฐฐ์ด A์ ๊ฐ์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค.
1. ์์ด๋์ด
๐ก rotate ์์๋ฅผ ์ ํ๋ ์์ดํจ์๋ฅผ ๋ง๋ฆ
๐ก ๊ฐ์ฅ ์์ ์ด์ ํฉ์ ์ฐพ๊ธฐ ์ํด ๋ฐฐ์ด์ ๋๋ฆด ๋ฒ์๋ฅผ ์ฐพ์
๐ก ๋ฐฐ์ด ๋๋ฆฌ๊ธฐ
๐ก ๋๋ฆฐ ํ, ๋ฐฐ์ด์ ํฉ ๊ณ์ฐํจ
2. ํต์ฌ ํ์ด
- rotate ์์๋ฅผ ์ ํ๋ ์์ดํจ์๋ฅผ ๋ง๋ฆ
static void dfs(int cnt) {
if(cnt == k) {
int[][] copy = new int[n][m];
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
copy[i][j] = map[i][j];
}
}
findMin(copy);
return;
}
for(int i=0; i<k; i++) {
if(!visited[i]) {
visited[i] = true;
result[cnt] = i;
dfs(cnt+1);
visited[i] = false;
}
}
}
- ๊ฐ์ฅ ์์ ์ด์ ํฉ์ ์ฐพ๊ธฐ ์ํด ๋ฐฐ์ด์ ๋๋ฆด ๋ฒ์๋ฅผ ์ฐพ์
static void findMin(int[][] copy) {
for(int i=0; i<result.length; i++) {
int idx = result[i];
int lx = op[idx][0] - op[idx][2] - 1;
int ly = op[idx][1] - op[idx][2] - 1;
int rx = op[idx][0] + op[idx][2] - 1;
int ry = op[idx][1] + op[idx][2] - 1;
rotate(lx, ly, rx, ry, copy);
}
cal(copy);
}
- ๋ฐฐ์ด ๋๋ฆฌ๊ธฐ
static void rotate(int lx, int ly, int rx, int ry, int[][] copy) {
if(lx == rx && ly == ry)
return;
int[] tmp = new int[3];
tmp[0] = copy[lx][ry];
tmp[1] = copy[rx][ry];
tmp[2] = copy[rx][ly];
for(int i = ry; i > ly; i--) {
copy[lx][i] = copy[lx][i-1];
}
for(int i = rx; i > lx; i--) {
if(i == lx + 1) copy[i][ry] = tmp[0];
else copy[i][ry] = copy[i - 1][ry];
}
for(int i = ly; i < ry; i++) {
if(i == ry - 1) copy[rx][i] = tmp[1];
else copy[rx][i] = copy[rx][i + 1];
}
for(int i = lx; i < rx; i++) {
if(i == rx - 1) copy[i][ly] = tmp[2];
else copy[i][ly] = copy[i + 1][ly];
}
rotate(lx + 1, ly + 1, rx - 1, ry - 1, copy);
}
- ๋๋ฆฐ ํ, ๋ฐฐ์ด์ ํฉ ๊ณ์ฐํจ
static void cal(int[][] copy) {
for(int i=0; i<copy.length; i++) {
int sum = 0;
for(int j=0; j<copy[i].length; j++) {
sum += copy[i][j];
}
min = Math.min(sum, min);
}
}
3. ์ฝ๋
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Imple_14 {
static int[][] map;
static int[][] op;
static int n, m, k;
static int min = Integer.MAX_VALUE;
static boolean[] visited;
static int[] result;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
k = Integer.parseInt(s[2]);
map = new int[n+1][m+1];
op = new int[k][3];
for(int i=0; i<n; i++) {
s = br.readLine().split(" ");
for(int j=0; j<m; j++) {
map[i][j] = Integer.parseInt(s[j]);
}
}
for(int i=0; i<k; i++) {
s = br.readLine().split(" ");
for(int j=0; j<3; j++) {
op[i][j] = Integer.parseInt(s[j]);
}
}
visited = new boolean[k];
result = new int[k];
dfs(0);
System.out.println(min);
}
static void dfs(int cnt) {
if(cnt == k) {
int[][] copy = new int[n][m];
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
copy[i][j] = map[i][j];
}
}
findMin(copy);
return;
}
for(int i=0; i<k; i++) {
if(!visited[i]) {
visited[i] = true;
result[cnt] = i;
dfs(cnt+1);
visited[i] = false;
}
}
}
static void findMin(int[][] copy) {
for(int i=0; i<result.length; i++) {
int idx = result[i];
int lx = op[idx][0] - op[idx][2] - 1;
int ly = op[idx][1] - op[idx][2] - 1;
int rx = op[idx][0] + op[idx][2] - 1;
int ry = op[idx][1] + op[idx][2] - 1;
rotate(lx, ly, rx, ry, copy);
}
cal(copy);
}
static void cal(int[][] copy) {
for(int i=0; i<copy.length; i++) {
int sum = 0;
for(int j=0; j<copy[i].length; j++) {
sum += copy[i][j];
}
min = Math.min(sum, min);
}
}
static void rotate(int lx, int ly, int rx, int ry, int[][] copy) {
if(lx == rx && ly == ry)
return;
int[] tmp = new int[3];
tmp[0] = copy[lx][ry];
tmp[1] = copy[rx][ry];
tmp[2] = copy[rx][ly];
for(int i = ry; i > ly; i--) {
copy[lx][i] = copy[lx][i-1];
}
for(int i = rx; i > lx; i--) {
if(i == lx + 1) copy[i][ry] = tmp[0];
else copy[i][ry] = copy[i - 1][ry];
}
for(int i = ly; i < ry; i++) {
if(i == ry - 1) copy[rx][i] = tmp[1];
else copy[rx][i] = copy[rx][i + 1];
}
for(int i = lx; i < rx; i++) {
if(i == rx - 1) copy[i][ly] = tmp[2];
else copy[i][ly] = copy[i + 1][ly];
}
rotate(lx + 1, ly + 1, rx - 1, ry - 1, copy);
}
}
4. ๊ฒฐ๊ณผ
์ฑ๊ณตโจ
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm] ๐ช๏ธ๋ฐฑ์ค 17144 ๋ฐฐ์ด ๋๋ฆฌ๊ธฐ4), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kha0318/Algorithm-๋ฐฑ์ค-17144-๋ฐฐ์ด-๋๋ฆฌ๊ธฐ4์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค