dx dy 알고리즘

• 좌표에 관련된 구현 문제를 풀 때 주로 사용한다.

• 현재 물체의 위치가 (2, 2) 일 때,
  - 위쪽(북쪽)으로 간다면 행 인덱스가 하나 줄어들어 (1, 2) 이 된다. 열은 바뀌지 않는다. (-1, 0)
  - 오른쪽(동쪽)으로 간다면 열 인덱스가 하나 늘어 (2, 3) 이 된다. 행은 바뀌지 않는다. (0, +1)
  - 아래쪽(남쪽)으로 간다면 행 인덱스가 하나 늘어 (3, 2) 가 된다. 열은 바뀌지 않는다. (+1, 0)
  - 왼쪽(서쪽)으로 간다면 열 인덱스가 하나 줄어들어 (2, 1) 이 된다. 행은 바뀌지 않는다. (0, -1)
• 위 규칙을 순서대로 dx, dy (x, y 증가율) 배열로 표현한다면 아래와 같다.

int dx[4] = { -1, 0, 1, 0 }; // 행 column
int dy[4] = { 0, 1, 0, -1 }; // 열 row

• 케이스 별로 나눠 물체의 위치를 계산하는 것보다, 이 배열을 사용하면 물체가 동서남북 방향으로 이동하는 것을 아주 쉽게 표현할 수 있다.

(1)
if (dir == "0") { // 북
	// 계산
} else if (dir == "1") { // 동
	// 계산 ...
    
(2)
x = x + dx[0]; y = y + dx[0]; // 북쪽 이동
x = x + dx[1]; y = y + dx[1]; // 동쪽 이동
x = x + dx[2]; y = y + dx[2]; // 남쪽 이동
x = x + dx[3]; y = y + dx[3]; // 서쪽 이동

• 만약 물체가 격자를 벗어날 것 같으면 이동 방향도 쉽게 바꿀 수 있다. 아래 코드의 (1), (2)번 방향 중 원하는 방향으로 선택해 넣으면 된다. (시계방향 : 0(북)→1(동)→2(남)→3(서), 반시계 : 0(북)→3(서)→2(남)→1(동))

• 이때, 반시계 방향으로 방향을 바꾸는 것은 꼭 4를 더해주어야 한다. 예를 들어 4를 더하지 않고 dir=0 일때 반시계 방향으로 회전하면, -1%4=1(파이썬은 3)이 된다. 이는 예상했던 결과와 다른 결과이다. 따라서 이를 방지하기 위해 4를 더한다. 어차피 4로 나눈 나머지 계산을 하므로 더해도 상관이 없다!

int inRange(int x, int y) {
	return x >= 0 && x < col && y >= 0 && y < row;
}

int main() {
	int x = 0;
    int y = 1;
    int dir = 0; // (0, 1)에 있는 물체가 북쪽으로 이동하면, (-1, 1)이 되므로 격자를 벗어나게 된다.
	if (!inRange(x+dx[dir], y+dy[dir]) { // 격자를 벗어나므로, 아래 코드 실행.
    	dir = (dir+1)%4;	// (1) 물체 이동방향을 시계 방향으로 회전
        dir = (4+(dir-1))%4;// (2) 물체 이동방향을 반시계 방향으로 회전
    }
}

---

예제

회오리 모양으로 격자 채우기 (바깥에서 안쪽으로)

• 바깥쪽에서 안쪽으로 갈 때는 격자의 범위를 벗어날 때, 그리고 진행할 곳에 이미 숫자가 채워져 있을 때 진행 방향을 바꾸면 된다.

int board[5][5];
int dx[4] = { -1, 0, 1, 0 }; // 행 column
int dy[4] = { 0, 1, 0, -1 }; // 열 row

int inRange(int x, int y) {
	return x >= 0 && x < 5 && y >= 0 && y < 5;
}

int main() {
	int x = 0, y = 0;
	int dir = 1;
	for (int num = 1; num <= 5*5; num++) {
    	board[x][y] = num;
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (!inRange(nx, ny) || board[nx][ny] != 0) {
        	dir = (dir+1)%4;
        }
        x = x + dx[dir];
        y = y + dy[dir];
    }
    return 0;
}

회오리 모양으로 격자 채우기 (안쪽에서 바깥쪽으로, 홀수)

• 중심으로부터 시작해서 격자의 유효범위의 간격을 조정하며 진행하면 된다. 중심으로부터 1x1, 3x3 ... 정사각형 격자로 살펴보면, 다음 크기의 격자로 넘어가기 전 마지막 숫자가 1, 9, 25 ... 홀수의 제곱수라는 것을 알 수 있다. 따라서 격자 범위를 뜻하는 dis 를 inRange() 계산에 추가하고, 만약 현재 격자 범위의 제곱수인 숫자가 채워진다면 격자 범위를 하나 늘리는 것으로 조정한다. (격자 범위는 중앙을 기준으로, 반지름을 뜻하기 때문에 2(dis+1)의 제곱수로 판단해야 한다.)

int board[5][5];
int dx[4] = { -1, 0, 1, 0 }; // 행 column
int dy[4] = { 0, 1, 0, -1 }; // 열 row
int dis = 0;

int inRange(int x, int y) {
	return x >= (5/2)-dis && x <= (5/2)+dis && y >= (5/2)-dis && y <= (5/2)+dis;
}

int main() {
	int x = 5/2, y = 5/2;
	int dir = 1;
	for (int num = 1; num <= 5*5; num++) {
    	board[x][y] = num;
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if ((2*(dis+1)-1)*(2*(dis+1)-1) == num) {
            dis++;
        }
        if (!inRange(nx, ny) || board[nx][ny] != 0) {
        	dir = (dir+1)%4;
        }
        x = x + dx[dir];
        y = y + dy[dir];
    }
    return 0;
}