구현 | 델타이동

💡사실 델타 이동은 알고리즘 문제를 풀기 위한 아이디어 중 하나이다. 완전탐색이나 그리디 같은 '알고리즘' 분류에 포함되는 것은 아니다.

델타를 이용한 2차 배열 탐색

2차 배열의 한 좌표에서 4방향의 인접 배열 요소를 탐색하는 방법

---

3*3 배열 가운데 좌표에서 돌아보기

int[][] arr = {{1,2,3}, {4,5,6}, {7,8,9}};
		
	int N = arr.length;
		
	// 현재(시작) 좌표
	int r = 1;
	int c = 1;
		
	// 상하좌우
	// 문제에서 방향을 명시했다면 그것대로, 아니라면 내가 편한대로 
	int[] dr = {-1,1,0,0};
	int[] dc = {0,0,-1,1};
		
	// nr, nc 현재 좌표
	for(int d=0; d<4; d++) {
		int nr = r + dr[d];
		int nc = c + dc[d];
			
		System.out.println(arr[nr][nc]);
	}

배열 범위를 넘어갈 수 있는 좌표에서 돌아보기

	r = 2;
	c = 1;
		
	for(int d=0; d<4; d++) {
		int nr = r + dr[d];
		int nc = c + dc[d];
			
		// 위치에 따라 ArrayIndexOutOfBoundsException 발생
		// 따라서 경계를 확인해야함
        // 가능한 경우 1, 2
		
        //	1) 내 품안에 있으면 작동
		if(nr>=0 && nr<N && nc>=0 && nc<N){
			System.out.println(arr[nr][nc]);
		}
		//	2) 내 품안에 들어오지 않으면 작동X
		if(nr<0 || nr>=N || nc<0 || nc>=N) 
			continue;
		System.out.println(arr[nr][nc]);

특정 좌표에 방문했는지 검사

⭕	r = 2;
	c = 1;
		
	for(int d=0; d<4; d++) {
		int nr = r + dr[d];
		int nc = c + dc[d];
     	if(nr>=0 && nr<N && nc>=0 && nc<N && arr[nr][nc]==5){
			System.out.println(1);
		}
	}

❌	r = 2;
	c = 1;
		
	for(int d=0; d<4; d++) {
		int nr = r + dr[d];
		int nc = c + dc[d];
     	if(arr[nr][nc]==5 && nr>=0 && nr<N && nc>=0 && nc<N){
			System.out.println(1);
		}
	}

⭕	for(int d=0; d<4; d++) {
		int nr = r + dr[d];
		int nc = c + dc[d];
     	if(nr<0 || nr>=N || nc<0 || nc>=N){
			continue;
		}
        if(arr[nr][nc]==5) {
        	System.out.println(1);
        }
        System.out.println(arr[nr][nc]);
	}

❌	for(int d=0; d<4; d++) {
		int nr = r + dr[d];
		int nc = c + dc[d];
     
        if(arr[nr][nc]==5) {
        	System.out.println(1);
        }
        if(nr<0 || nr>=N || nc<0 || nc>=N){
			continue;
		}
        System.out.println(arr[nr][nc]);
	}

논리연산자 &&와 || 연산자

❌의 경우, 인덱스가 범위 내에 있는지 검사하지 않은 채 5인 값인 곳부터 찾았기 때문이다. 올바르게 작동하는 경우는 인덱스 검사부터 하기 때문에 인덱스 범위를 벗어나는 좌표는 걸러진다. 따라서 조건을 작성하는 순서는 중요하다.

👉P&&Q
P가 거짓이면 Q는 검사도 하지 않는다. 결국은 F이므로
👉P||Q
P가 참이면 Q는 검사도 하지 않는다. 결국은 T이므로

델타표현

int[] dr = {-1,1,0,0};
int[] dc = {0,0,-1,1};

for(int d=0; d<4; d++) {
	int nr = r + dr[d];
	int nc = c + dc[d];
}

int[][] drc = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

for(int d=0; d<4; d++) {
	int nr = r + drc[d][0];
	int nc = c + drc[d][1];
}