[TIL-260223] 알고리즘: 2차원 배열의 순회, 델타 탐색

배열 순회

• 행 우선 순회

  int i; // 행의 좌표
  int j; // 열의 좌표

  int[][] arr= {{1,2,3},{4,5,6},{7,8,10}};

  int N = arr.length; // 행의 길이
  int M = arr[0].length; // 열의 길이

  for (int i = 0; i < N; i++) {
      for(int j = 0; j < M; j++) {        
          System.out.printf("%3d", arr[i][j]);
      }
      System.out.println();
  }

 

• 행 역 우선 순회
   

  int i; // 행의 좌표
  int j; // 열의 좌표

  int[][] arr= {{1,2,3},{4,5,6},{7,8,10}};

  int N = arr.length; // 행의 길이
  int M = arr[0].length; // 열의 길이

  for (int i = 0; i < N; i++) {
      for(int j = M-1; j >= 0; j--) {   // 마지막 인덱스 열부터 0까지
          System.out.printf("%3d", arr[i][j]);
      }
      System.out.println();
  }

• 열 우선 순회
   

  int i; // 행의 좌표
  int j; // 열의 좌표

  int[][] arr= {{1,2,3},{4,5,6},{7,8,10}};

  int N = arr.length; // 행의 길이
  int M = arr[0].length; // 열의 길이

  for (int j = 0; j < M; j++) { 	 // 열 먼저
      for(int i = 0; i < N; i++) {     // 행 나중에
          System.out.printf("%3d", arr[i][j]);
      }
      System.out.println();
  }

 

• 열 역 우선 순회

  int i; // 행의 좌표
  int j; // 열의 좌표

  int[][] arr= {{1,2,3},{4,5,6},{7,8,10}};

  int N = arr.length; // 행의 길이
  int M = arr[0].length; // 열의 길이

  for (int j = 0; j < M; j++) {    // 열 먼저
      for(int i = M-1; i >= 0; i--) {        // 마지막 인덱스 행부터 0까지
          System.out.printf("%3d", arr[i][j]);
      }
      System.out.println();
  }

 

• 지그재그 순회

  int i; // 행의 좌표
  int j; // 열의 좌표

  int[][] arr= {{1,2,3},{4,5,6},{7,8,10}};

  int N = arr.length; // 행의 길이
  int M = arr[0].length; // 열의 길이

  for (int i = 0; i < N; i++) {
      //정방향
      if(i % 2 == 0) {
          for(int j = 0; j < M; j++) {
              System.out.printf("%3d", arr[i][j]);
          }
      } else { // 역방향
          for(int j = M-1; j >= 0;j--) {
              System.out.printf("%3d", arr[i][j]);
          }
      }
      System.out.println();
  }

 

---

델타 탐색

2차원 배열의 한 좌표에서 4방향(혹은 8방향)의 인접 배열 요소를 탐색하는 방법

• 4방 탐색

public class Search_Delta4 {
	public static void main(String[] args) {
		int[][] arr = {{1,2,3},{4,5,6},{7,8,10}};
		// N*N
		int N = arr.length;
		// 현재 나의 좌표
		int r = 0, c = 0;
		// 상하좌우
		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];
			// 위치에 따라 문제 발생 할 수 있다
			// 경계확인 (둘 중 하나 선택)
			// 1. 범위안
			if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
				System.out.println(arr[nr][nc]);
			}
			// 2. 범위 안이 아니면 안하겠다(버리기)
			if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
			System.out.println(arr[nr][nc]);
		}
	}
}

• 8방 탐색

public class Search_Delta8 {
	public static void main(String[] args) {
		int[][] arr = {{1,2,3},{4,5,6},{7,8,10}};
		// N*N
		int N = arr.length;
		// 현재 나의 좌표
		int r = 0, c = 0;
		// 상, 우상, 우, 우하, 하, 좌하, 좌, 좌상
		int[] dr = {-1, -1, 0, 1, 1, 1, 0, -1};
		int[] dc = {0, 1, 1, 1, 0, -1, -1, -1};
		for (int d = 0; d < 8; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			// 위치에 따라 문제 발생 할 수 있다
			// 경계확인 (둘 중 하나 선택)
			// 1. 범위안
			if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
				System.out.println(arr[nr][nc]);
			}
			// 2. 범위 안이 아니면 안하겠다(버리기)
			if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
			System.out.println(arr[nr][nc]);
		}
	}
}

 

---

❕느낀점

알고리즘 문제 풀이에 대한 시야가 한층 넓어진 느낌이었다.

 

최근 코테 문제를 풀면서 비교적 쉽고 간단한 문제(백준 브론즈 수준)는 그래도 시간이 주어지면 스스로 해결할 수 있었다. 하지만 2차원 배열이 등장하는 복잡한 문제만 보면 머리가 하얘지고, 어디서부터 접근해야 할지 감조차 오지 않았다. 

 

오늘 수업을 통해, 2차원 배열 순회 방법에 대한 이해가 부족했고 델타 탐색에도 익숙하지 않았던 점이 문제의 핵심 원인이었음을 깨달았다. 오늘 SWEA 달팽이 숫자 문제를 풀며 델타 탐색을 활용해 문제를 해결할 수 있었고, 비록 문제 풀이에 거의 1시간을 썼지만 이전보다 한단계 더 어려운 문제를 풀어냈다는 점에서 의미 있는 진전이었다.

 

아직은 복잡한 알고리즘 문제 풀이가 익숙하지 않아 어렵게 느껴지지만 앞으로도 차근차근 꾸준히 실력을 쌓아가야겠다.