[Algorithm] 델타값을 이용한 상하좌우 탐색

https://www.acmicpc.net/problem/1012

 

백준 1012 문제를 풀다가 나온 스킬이다. 자주 사용되므로 숙지해두자.

 

문제에서 2차원 배열에 있는 모든 원소를 하나씩 살펴보면서 그 원소의 상하좌우 원소도 검사하는 작업이 있었다.

여기에서 반복문을 통해 x와 y에 델타값을 더해 매우 편하게 상하좌우 탐색을 할 수 있다.

 

구현 순서는 다음과 같다. (이 정도는 외우자)

• 탐색에 사용할 델타값 배열 만들기
• 기존 좌표에 델타값을 더한 새로운 좌표 구하기
• 새로운 좌표가 배열 인덱스 범위 안에 있는지 검사하기

전체 코드는 다음과 같다. (DFS 코드 안에 들어가 있으므로 for문 안쪽만 보면 된다)

// 탐색에 사용할 델타값
// 상, 하, 좌, 우 순서로 이동
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};

void DFS(int X, int Y)
{
	// 방문 처리
	matrix[Y][X] = 0;

	// 델타 탐색 후 1이 발견되면 발견된 곳으로 이동해서 다시 BFS 시행
	for (int i = 0; i < 4; i++)
	{
		// 배열 인덱스 조절
		int nextX = X + dx[i];
		int nextY = Y + dy[i];
		if (nextX >= m || nextX < 0 || nextY >= n || nextY < 0)
		{
			continue;
		}	

		if (matrix[nextY][nextX] == 1)
		{
			//PrintMatrix();
			//printf("Move to (%d, %d)\n", nextX, nextY);
			DFS(nextX, nextY);
		}
	}
}

하나씩 살펴보자.

// 탐색에 사용할 델타값
// 상, 하, 좌, 우 순서로 이동
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};

탐색에 사용할 델타 값이다. 미리 정한 순서인 상->하->좌->우 의 순서로 움직일 것이므로 y의 델타값은 -1, 1, 0, 0이고 x의 델타값은 0, 0, -1, 1이 된다.

 

만약 대각선으로 움직이고 싶다면 다음과 같이 하면 된다

// 탐색에 사용할 델타값
// 상, 하, 좌, 우, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 이동
int dy[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dx[8] = {0, 0, -1, 1, -1, 1, -1, 1};

for (int i = 0; i < 4; i++)

이동 방향은 상하좌우 네 가지 밖에 없으므로 반복문은 항상 4회만 실행된다.

// 배열 인덱스 조절
int nextX = X + dx[i];
int nextY = Y + dy[i];
if (nextX >= m || nextX < 0 || nextY >= n || nextY < 0)
{
    continue;
}

현재 위치 X, Y에 델타 값을 더해 새로운 값을 만들어준다. 그리고 2차원 배열에서 이동할 때 인덱스 밖으로 벗어나는 것을 방지하기 위해 이동할 좌표가 배열의 범위 안에 있는 지 검사하고, 밖으로 나갔다면 해당 방향으로의 이동은 건너 뛴다.