[코딩테스트 유형 정리]dx, dy 테크닉

dx, dy 테크닉은 2차원 배열이나 격자 문제를 해결할 때 자주 사용되는 기법이다. 보통 상하좌우 4방향 또는 8방향으로의 이동을 효율적으로 처리하기 위해 사용된다.

기본 개념

dx, dy 배열은 각각 x 와 y 좌표의 변화를 나타내며, 방향을 인덱스로 지정해 특정 방향으로 이동할 때 좌표를 어떻게 변화시킬지를 저장한다. dx는 행 방향 이동, dy는 열 방향 이동으로 생각하면 된다.

상하좌우 4방향 이동

4방향으로 이동하려면 다음과 같은 dx, dy 배열을 사용할 수 있다.

int[] dx = {-1, 1, 0, 0}; // 행 방향 이동 (-1 : 위, +1 : 아래)
int[] dy = {0, 0, -1, 1}; // 열 방향 이동 (-1 : 왼쪽, +1 : 오른쪽)

인덱스

인덱스	dx	dy	이동 방향
0	-1	0	위
1	1	0	아래
2	0	-1	왼쪽
3	0	1	오른쪽

x = 1, y = 1인 경우

사용예시 1

이러한 배열을 사용해 인접한 좌표로 쉽게 이동할 수 있다. 예를 들어, (x, y)에서 인접한 모든 좌표를 이동하고 싶을 때, 다음과 같이 반복문을 사용할 수 있다.

int[] dx = {-1, 1, 0, 0}; 
int[] dy = {0, 0, -1, 1};

for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		
		// 배열의 범위를 벗어나는지 체크 
		if (nx >= 0 && nx < N && ny >= 0; ny < M) {
		}
}

사용예시 2

이동 방향이 오 → 아 → 왼 → 위 가 반복되는 경우

// 방향 설정 : 오른쪽(0), 아래(1), 왼쪽(2), 위(3)
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};

int[][] arr = new int[N][N];

int num = 1;
int x = 0, y = 0; // 시작 좌표 (0, 0)
int direction = 0; // 초기 방향 : 오른쪽
		
		
		while (num <= N*N) {
			arr[x][y] = num++;
			
			// 다음칸으로 이동할 좌표 계산
			int nx = x + dx[direction];
			int ny = y + dy[direction];
			
			// 이동할 좌표가 범위를 벗어나거나 이미 숫자가 채워져 있으면 방향을 바꿈
			if (nx < 0 || nx >= N || ny < 0 || ny >= N || arr[nx][ny] != 0) {
				direction = (direction + 1) % 4;
				nx = x + dx[direction];
				ny = y + dy[direction];
			}
			
			// 새로운 위치로 이동 
			x = nx;
			y = ny;
			
		}

8방향 이동

상하좌우와 대각선까지 포함한 8방향으로 이동하려면 dx, dy 배열에 추가 방향을 넣어 사용할 수 있다.

// 8방향 (상, 하, 좌, 우, 좌상, 우상, 좌하, 우하)
int[] dx = { -1, 1, 0, 0, -1, -1, 1, 1 };
int[] dy = { 0, 0, -1, 1, -1, 1, -1, 1 };