현재의 좌표를 (i, j)라고 했을 때 상, 하, 좌, 우로 한 칸 움직이기 위해서는 다음과 같습니다.
int[] dx = {-1, 1, 0, 0}; // 순서대로 상, 하, 좌, 우
int[] dy = {0, 0, -1, 1};
for(int d=0; d<4; d++){
int nx = i + dx[d];
int ny = j + dy[d];
}
그러면, 한 쪽 방향으로 벽이나 다른 숫자에 부딪칠 때 까지 움직이기 위해서는 어떻게 해야 할까요?
이의 관한 문제로는 백준 2048(Easy), 구슬 탈출 2 문제 등이 있습니다.
| 2048(Easy) | 구슬 탈출 2 |
| https://www.acmicpc.net/problem/12100 | https://www.acmicpc.net/problem/13460 |
위로 움직이기 위해서 아래와 같은 반복문을 사용해 쭉 이동시킵니다.
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n; j++) {
...
}
}
아래로 움직이기 위해서 아래와 같은 반복문을 사용합니다.
for (int i = n-1; i > 0; i--) {
for (int j = 0; j < n; j++) {
...
}
}
좌로 움직이기 위해서 아래와 같은 반복문을 사용합니다.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n-1; j++) {
...
}
}
우로 움직이기 위해서 아래와 같은 반복문을 사용합니다.
for (int i = 0; i < n; i++) {
for (int j = n-1; j > 0; j--) {
...
}
}
일반 반복문은 초기식, 조건식, 변화식으로 이루어져 있습니다.
네 개 방향 모두 이중 반복문이 필요합니다.
하지만, 이동 방향에 따라 초기식, 조건식, 변화식이 조금씩 다릅니다.
이를 추상화 해 볼 수 있지 않을까요?
초기식을 추상화해보겠습니다.
좌표는 (i, j)로 두 개를 사용합니다.
이는 일반 변수에 저장해서 방향에 따라 변화시키면 됩니다.
// 상, 좌는 0 부터 시작
int startRow = 0; // i
int startColumn = 0; // j
if (d == Direction.DOWN) { // 아래
startRow = n - 1;
} else if (d == Direction.RIGHT) { // 우측
startColumn = n - 1;
}
조건식을 추상화해보겠습니다.
조건식은 bool 값입니다.
즉, Predicate를 사용할 수 있습니다.
// 상, 좌는 조건식이 n보다 작음
Predicate<Integer> rowPredicate = (i) -> (i < n);
Predicate<Integer> columnPredicate = (j) -> (j < n);
if (d == Direction.DOWN) { // 아래
rowPredicate = (i) -> (i >= 0);
} else if (d == Direction.RIGHT) { // 우측
columnPredicate = (j) -> (j >= 0);
}
변화식을 추상화해보겠습니다.
방향에 따라 1이 더해지거나 빼집니다.
이는 방향 순서를 정하고 그 순서에 맞에 배열에서 값을 가져와 더하면 됩니다.
/*
상 : i++, j++
하 : i--, j++
좌 : i++, j++
우 : i++, j--
*/
int[] ix = new int[]{1, -1, 1, 1}; // 상, 하, 좌, 우
int[] jy = new int[]{1, 1, 1, -1};
i += ix[d]
j += jy[d]
이를 하나의 클래스로 추상화하면, 다음과 같이 만들어 사용할 수 있습니다.
private enum Direction {
UP(0),
DOWN(1),
LEFT(2),
RIGHT(3);
private final int value;
Direction(int value, int[] dxdy) {
this.value = value;
}
}import java.util.function.Predicate;
private static class MoveCondition {
int startRow, startColumn;
Predicate<Integer> rowPredicate, columnPredicate;
int[] ix, jy;
private MoveCondition(int startRow, int startColumn,
Predicate<Integer> rowPredicate,
Predicate<Integer> columnPredicate) {
this.startRow = startRow;
this.startColumn = startColumn;
this.rowPredicate = rowPredicate;
this.columnPredicate = columnPredicate;
this.ix = new int[]{1, -1, 1, 1};
this.jy = new int[]{1, 1, 1, -1};
}
private boolean test(Predicate<Integer> predicate, Integer value) {
return predicate.test(value);
}
private static MoveCondition of(Direction d, int n) {
int startRow = 0;
int startColumn = 0;
Predicate<Integer> rowPredicate = (i) -> (i < n);
Predicate<Integer> columnPredicate = (j) -> (j < n);
if (d == Direction.DOWN) {
startRow = n - 1;
rowPredicate = (i) -> (i >= 0);
} else if (d == Direction.RIGHT) {
startColumn = n - 1;
columnPredicate = (j) -> (j >= 0);
}
return new MoveCondition(startRow, startColumn, rowPredicate, columnPredicate);
}
}MoveCondition mc = MoveCondition.of(d, n);
for (int i = mc.startRow; mc.test(mc.rowPredicate, i); i += mc.ix[d.value]) {
for (int j = mc.startColumn; mc.test(mc.columnPredicate, j); j += mc.jy[d.value]) {
...
}
}
위의 더보기를 클릭하면 됩니다.
근데, 무조건 위와 같이 추상화 하는게 좋을까요?
저는 위의 방법을 백준의 12100번 문제인 2048(Easy)을 풀고, 리팩토링하다가 생각난 방법입니다.
저는 12100을 백트랙킹으로 풀었습니다.
즉, 가지치기를 하더라도 그 경우의 수가 많습니다.
리팩토링을 하기 전에는 다음과 같은 메모리와 속도에 풀 수 있었습니다.
리팩토링 후에는 다음과 같은 메모리와 속도에 풀 수 있었습니다.
속도가 더 느려지고, 메모리의 사용량이 거의 3배가 증가했습니다.
아무래도 객체를 탐색할 때 마다 생성하니 그런거 같습니다.
코드가 객체지향적으로 변해 유지보수가 쉬워진 것에 대해 이점이 있지만,
알고리즘 메모리와 속도의 단점을 매울 만큼의 이점이 있는지에 대해 생각을 해 봐야할 거 같습니다...
