[Java]좌표 이동/탐색

*좌표 이동/탐색

-> DFS/BFS 문제를 접하다 보면, 좌표의 성질을 갖는 대상의 원소에서 다른 원소로 이동하거나, 그 주변을 탐색해야하는 로직이 빈번하게 사용된다. 

 

*2차원 배열 좌표와 행렬

-> 2차원 배열의 인덱스별 값이 생기는 위치를 시각화하여 생각해보면 평면을 떠올릴 수 있고, 평면은 일상 생활에서 보통 좌표를 이용하여 나타낸다.

-> 일반적으로 수학에서 좌표의 1사분면은, 다음과 같은 모양을 가진다.

수학의 좌표 평면 1사분면

즉, x값이 증가할수록 오른 쪽으로 이동하고,  y값이 증가할수록 위 쪽으로 이동하는 구조를 가진다. 그렇지만, 일반적으로 2차원 배열을 형성하는 경우 인덱스 별 값이 생기는 위치는 논리적으로 좌표 평면 1사분면의 구조처럼 평면이 만들어지지 않는다.

-> 2차원 배열을 형성하는 경우는 다음과 같이 좌표 평면의 3사분면의 모양과 같이 논리적 평면이 생기지만, 좌표 평면의 3사분면과 다른점은 아래 쪽으로 이동할 수록 y값이 증가한다는 사실이다. 

 따라서 2차원 배열의 인덱스별 값의 위치를 평면화하여 생각하는 경우는 행렬을 바탕으로 생각하는 것이 더 편리하다.

 

*방향

-> 어떤 대상을 기준으로 어디로 움직일 것 인가 혹은 어디로 탐색할 것 인가를 고민하기 위해서는 방향을 먼저 설정해주어야 한다. 방향을 표현하는 방법은 대표적으로 아래 두 가지 방법이 있다. 자신에게 맞는 방법을 적절히 활용하도록 하자.

※ 두 개의 일차원 배열을 이용하여 방향을 나타내는 방법

// 상하좌우
int[] dr = { -1, 1, 0, 0 };
int[] dc = { 0, 0, -1, 1 };

-> 2차원 배열의 인덱스 별 값의 위치는 행렬을 기반으로 생각하여야 한다고 했다. 즉, 행렬을 기준으로 어떤 수의 위에 있으면 행이 감소하고 열은 그대로 유지할 것이기 때문에 dr[0] = -1, dc[0] = 0의 값을 갖는다. 마찬가지 방법을 통해 아래, 왼쪽, 오른쪽 방향도 표현할 수 있다.

※ 이차원 배열을 이용하여 방향을 나타내는 방법

// 상하좌우
int[][] drdc = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

-> 위의 로직과 다른 것이 없다. 2차원 배열의 1열이 행의 방향을 의미하고, 2열이 열의 방향을 의미한다고 생각한 뒤 이를 한 번에 저장해준 것 뿐이다.

 

*이동

-> 이를 테면, false으로 초기화된 boolean 2차원 배열에서 이동명령에 따라 이동하는 위치마다 true로 바꾸는 경우는 다음과 같이 구현할 수 있다.

import java.util.Arrays;
import java.util.Scanner;

public class Move {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 상하좌우
		int[] dr = { -1, 1, 0, 0 };
		int[] dc = { 0, 0, -1, 1 };
		// 방향을 저장할 변수(기본 방향은 상).
		int dir = 0;
		// 맵
		boolean[][] map = new boolean[3][3];

		// 명령 입력, 0행 0열부터 시작.
		System.out.print("이동 명령을 입력하세요(Ex : RRDDRDL) : ");
		String move = sc.nextLine();
		map[0][0] = true;
		int r = 0, c = 0;

		// 이동
		for (int i = 0; i < move.length(); i++) {
			char a = move.charAt(i);
			System.out.println("움직일 방향 출력 : " + a);
			// 각 문자를 해석해 맞는 방향을 세팅 해준다.
			switch (a) {
			case 'U':
				dir = 0;
				break;
			case 'D':
				dir = 1;
				break;
			case 'L':
				dir = 2;
				break;
			case 'R':
				dir = 3;
				break;
			}
			// 이동.
			r += dr[dir];
			c += dc[dir];
			map[r][c] = true;
			// 현재 맵의 상태 출력
			for(int j = 0; j < 3; j++) {
				System.out.println(Arrays.toString(map[j]));
			}
			System.out.println();
		}
		sc.close();
	}
}

출력 결과

-> 보통 알고리즘 문제를 푸는 경우, 주어진 평면의 바깥으로 나가는 경우(인덱스 범위를 초과하는 경우)를 고려해야하는 로직이 많다. 이 경우, 다음 인덱스를 미리 저장하고 테스트해볼 변수를 새로 선언하여 문제를 해결한다.

import java.util.Arrays;
import java.util.Scanner;

public class Move {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 상하좌우
		int[] dr = { -1, 1, 0, 0 };
		int[] dc = { 0, 0, -1, 1 };
		// 방향을 저장할 변수(기본 방향은 상).
		int dir = 0;
		// 맵
		boolean[][] map = new boolean[3][3];

		// 명령 입력, 0행 0열부터 시작.
		System.out.print("이동 명령을 입력하세요(Ex : RRDDRDL)(바깥으로 나가면 함수 종료) : ");
		String move = sc.nextLine();
		map[0][0] = true;
		int r = 0, c = 0;
		// 임시로 이동할 좌표를 먼저 설정.
		int nr, nc;

		// 이동
		for (int i = 0; i < move.length(); i++) {
			char a = move.charAt(i);
			System.out.println("움직일 방향 출력 : " + a);
			// 각 문자를 해석해 맞는 방향을 세팅 해준다.
			switch (a) {
			case 'U':
				dir = 0;
				break;
			case 'D':
				dir = 1;
				break;
			case 'L':
				dir = 2;
				break;
			case 'R':
				dir = 3;
				break;
			}
			// 임시로 이동
			nr = r + dr[dir];
			nc = c + dc[dir];
			// 바깥으로 이동하는지 체크하는 if 제어문!!
			if (0 <= nr && nr < 3 && 0 <= nc && nc < 3) {
				r = nr;
				c = nc;
				map[r][c] = true;
			} else {
				System.out.println("바깥으로 이동할 수 없습니다.");
                sc.close();
				return;
			}
			// 현재 맵의 상태 출력
			for (int j = 0; j < 3; j++) {
				System.out.println(Arrays.toString(map[j]));
			}
			System.out.println();
		}
		sc.close();
	}
}

*탐색

-> 탐색도 이동과 크게 다를 것 없다. 어떤 인덱스의 위치를 기준으로, 순차적으로 주변을 탐색하고 싶은 경우에는 우선 방향을 잘 설정해주면 된다.

※ 상하좌우 <4방향>

// 상하좌우
int[] dr = { -1, 1, 0, 0 };
int[] dc = { 0, 0, -1, 1 };

※ 12시, 1시, 3시, 5시, 6시, 7시, 9시, 11시 <8방향>

// 12시, 1시, 3시, 5시, 6시, 7시, 9시, 11시
int[] dr = { -1, -1, 0, 1, 1, 1, 0, -1 };
int[] dc = { 0, 1, 1, 1, 0, -1, -1, -1};

-> 이를 테면, 3x3 int 배열의 특정 인덱스의 8방향에 3이라는 숫자가 몇개 있는지 탐색하는 경우는 다음과 같이 구현할 수 있다.

import java.util.Scanner;

public class Search {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int[][] map = new int[3][3];
		System.out.println("배열에 넣을 숫자를 입력하세요.");
		// 3,3 int 배열에 입력된 숫자를 대입한다.
		for (int i = 0; i < 3; i++) {
			String line = sc.nextLine();
			for (int j = 0; j < 3; j++) {
				map[i][j] = line.charAt(j) - '0';
			}
		}

		// 탐색할 좌표 입력
		int r = sc.nextInt();
		int c = sc.nextInt();

		// 3의 개수 파악.
		int cnt = 0;
		// 12시, 1시, 3시, 5시, 6시, 7시, 9시, 11시
		int[] dr = { -1, -1, 0, 1, 1, 1, 0, -1 };
		int[] dc = { 0, 1, 1, 1, 0, -1, -1, -1 };
		for (int i = 0; i < 8; i++) {
			if (map[r + dr[i]][c + dc[i]] == 3) {
				cnt++;
			}
		}
		// 결과 출력
		System.out.println(cnt);
		sc.close();
	}
}