2차원 배열을 행(가로) 기준으로 왼쪽에서 오른쪽으로 순회한 뒤, 다음 행으로 이동하여 반복하는 방식
▼ 단계별 시각화
- 원본 행렬:
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
1단계: 첫 번째 행 순회
[1, 2, 3] 순서: 1 → 2 → 3
[4, 5, 6]
[7, 8, 9]
2단계: 두 번째 행 순회
[1, 2, 3]
[4, 5, 6] 순서: 4 → 5 → 6
[7, 8, 9]
3단계: 세 번째 행 순회
[1, 2, 3]
[4, 5, 6]
[7, 8, 9] 순서: 7 → 8 → 9
최종 순회 순서: 1→2→3→4→5→6→7→8→9
▼ 동작 원리
1. 행 반복문(바깥쪽)과 열 반복문(안쪽) 설정
1-1. 행 인덱스 i는 0부터 행의 크기-1까지 반복
1-2. 열 인덱스 j는 0부터 열의 크기-1까지 반복
2. 현재 위치(i,j)의 원소에 접근
2-1. arr[i][j] 형태로 각 원소에 접근
3. 다음 행으로 이동하여 반복
3-1. 현재 행의 순회가 끝나면 다음 행으로 이동
▼ 구현 코드
public class MatrixTraversal {
public static void rowMajorOrder(int[][] arr) {
int rows = arr.length;
int cols = arr[0].length;
// 1. 행 반복문(바깥쪽)과 열 반복문(안쪽) 설정
// 1-1. 행 인덱스 i는 0부터 행의 크기-1까지 반복
for (int i = 0; i < rows; i++) {
// 1-2. 열 인덱스 j는 0부터 열의 크기-1까지 반복
for (int j = 0; j < cols; j++) {
// 2. 현재 위치(i,j)의 원소에 접근
// 2-1. arr[i][j] 형태로 각 원소에 접근
System.out.print(arr[i][j] + " ");
}
// 3. 다음 행으로 이동하여 반복
// 3-1. 현재 행의 순회가 끝나면 다음 행으로 이동
System.out.println();
}
}
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
System.out.println("행 우선 순회 결과:");
rowMajorOrder(matrix);
}
}
2차원 배열을 열(세로) 기준으로 위에서 아래로 순회한 뒤, 다음 열로 이동하여 반복하는 방식
▼ 단계별 시각화
- 원본 행렬:
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
1단계: 첫 번째 열 순회
[1, 2, 3] 순서: 1
[4, 5, 6] ↓
[7, 8, 9] 4
↓
7
2단계: 두 번째 열 순회
[1, 2, 3] 순서: 2
[4, 5, 6] ↓
[7, 8, 9] 5
↓
8
3단계: 세 번째 열 순회
[1, 2, 3] 순서: 3
[4, 5, 6] ↓
[7, 8, 9] 6
↓
9
최종 순회 순서: 1→4→7→2→5→8→3→6→9
▼ 동작 원리
1. 열 반복문(바깥쪽)과 행 반복문(안쪽) 설정
1-1. 열 인덱스 j는 0부터 열의 크기-1까지 반복
1-2. 행 인덱스 i는 0부터 행의 크기-1까지 반복
2. 현재 위치(i,j)의 원소에 접근
2-1. arr[i][j] 형태로 각 원소에 접근
2-2. 각 열을 위에서 아래로 순회
3. 다음 열로 이동하여 반복
3-1. 현재 열의 순회가 끝나면 다음 열로 이동
▼ 구현 코드
public class MatrixTraversal {
public static void columnMajorOrder(int[][] arr) {
int rows = arr.length;
int cols = arr[0].length;
// 1. 열 반복문(바깥쪽)과 행 반복문(안쪽) 설정
// 1-1. 열 인덱스 j는 0부터 열의 크기-1까지 반복
for (int j = 0; j < cols; j++) {
// 1-2. 행 인덱스 i는 0부터 행의 크기-1까지 반복
for (int i = 0; i < rows; i++) {
// 2. 현재 위치(i,j)의 원소에 접근
// 2-1. arr[i][j] 형태로 각 원소에 접근
// 2-2. 각 열을 위에서 아래로 순회
System.out.print(arr[i][j] + " ");
}
// 3. 다음 열로 이동하여 반복
// 3-1. 현재 열의 순회가 끝나면 다음 열로 이동
System.out.println();
}
}
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
System.out.println("열 우선 순회 결과:");
columnMajorOrder(matrix);
}
}
- 원본 배열:
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
1단계: 첫 번째 행 순회 (왼쪽 → 오른쪽)
[1 → 2 → 3] (순회하는 행)
[4, 5, 6]
[7, 8, 9]
2단계: 두 번째 행 순회 (오른쪽 → 왼쪽)
[1, 2, 3]
[4 ← 5 ← 6] (순회하는 행)
[7, 8, 9]
3단계: 세 번째 행 순회 (왼쪽 → 오른쪽)
[1, 2, 3]
[4, 5, 6]
[7 → 8 → 9] (순회하는 행)
최종 순회 순서: 1→2→3→6→5→4→7→8→9
▼ 동작 원리
접근방법:
- 2차원 배열을 행 단위로 순회하되, 행의 인덱스에 따라 순회 방향을 달리함
- 행 인덱스의 짝/홀수 여부를 확인하여 순회 방향 결정
세부구현:
1. 행 인덱스에 따른 순회 방향 결정
1-1. 행 인덱스(i)가 짝수인 경우: 왼쪽에서 오른쪽으로 순회
1-2. 행 인덱스(i)가 홀수인 경우: 오른쪽에서 왼쪽으로 순회
2. 각 행의 원소 순회
2-1. 짝수 행: j를 0부터 열의 크기-1까지 증가
2-2. 홀수 행: j를 열의 크기-1부터 0까지 감소
3. 다음 행으로 이동하여 반복
3-1. 현재 행의 순회가 끝나면 다음 행으로 이동
▼ 구현 코드
public class MatrixTraversal {
public static void zigzagOrder(int[][] arr) {
int rows = arr.length;
int cols = arr[0].length;
// 1. 행 인덱스에 따른 순회 방향 결정
for (int i = 0; i < rows; i++) {
// 1-1. 행 인덱스(i)가 짝수인 경우: 왼쪽에서 오른쪽으로 순회
if (i % 2 == 0) {
// 2-1. 짝수 행: j를 0부터 열의 크기-1까지 증가
for (int j = 0; j < cols; j++) {
System.out.print(arr[i][j] + " ");
}
}
// 1-2. 행 인덱스(i)가 홀수인 경우: 오른쪽에서 왼쪽으로 순회
else {
// 2-2. 홀수 행: j를 열의 크기-1부터 0까지 감소
for (int j = cols - 1; j >= 0; j--) {
System.out.print(arr[i][j] + " ");
}
}
// 3. 다음 행으로 이동하여 반복
// 3-1. 현재 행의 순회가 끝나면 다음 행으로 이동
System.out.println();
}
}
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
System.out.println("지그재그 순회 결과:");
zigzagOrder(matrix);
}
}
접근방법:
- 델타 배열 활용: 우 → 하 → 좌 → 상 순서로 이동 방향을 (dx, dy)로 정의
- 유효성 검사 후 이동: 현재 위치에서 다음 위치로 이동하기 전,
다음 위치가 배열 범위 내에 있고 방문하지 않은 칸인지 검사
- 이동 방향 전환: 다음 위치가 배열 범위 밖이거나 이미 방문한 칸일 경우,
시계 방향으로 방향을 변경한 뒤 다시 이동 시도
세부구현:
1. 방향 설정을 위한 델타 배열 정의
1-1. 우, 하, 좌, 상 순서로 이동 방향 배열 생성
1-2. dx = [1, 0, -1, 0], dy = [0, 1, 0, -1]
2. 현재 위치에서 이동 처리
2-1. 현재 위치 방문 및 방문 처리
2-2. 현재 방향(dir)에 따라 다음 위치(nextRow, nextCol) 계산
2-3. 다음 위치 유효성 확인 (배열 범위 내 & 미방문)
- 유효하다면 다음 위치로 이동
- 유효하지 않다면 방향 전환(dir = (dir + 1) % 4) 후 재시도
3. 모든 원소를 방문할 때까지 2단계를 반복
▼ 구현 코드
public class Solution {
public static void main(String[] args) {
// 예시 행렬 (3x4 행렬)
int[][] matrix = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
printSnailOrder(matrix);
}
public static void printSnailOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0) return;
int N = matrix.length; // 행의 크기
int M = matrix[0].length; // 열의 크기
boolean[][] visited = new boolean[N][M];
// 1. 방향 설정을 위한 델타 배열 정의
// 1-1. 우, 하, 좌, 상 순서로 이동 방향 배열 생성
// 1-2. dx = [1, 0, -1, 0], dy = [0, 1, 0, -1]
int[] dy = {0, 1, 0, -1}; // 행 이동
int[] dx = {1, 0, -1, 0}; // 열 이동
int x = 0, y = 0; // 현재 위치
int dir = 0; // 현재 방향 (0: 우, 1: 하, 2: 좌, 3: 상)
// 3. 모든 원소를 방문할 때까지 2단계를 반복
for (int i = 0; i < N * M; i++) {
// 2. 현재 위치에서 이동 처리
// 2-1. 현재 위치 방문 및 방문 처리
System.out.print(matrix[y][x] + " ");
visited[y][x] = true;
// 2-2. 현재 방향(dir)에 따라 다음 위치(nextRow, nextCol) 계산
int nextX = x + dx[dir];
int nextY = y + dy[dir];
// 2-3. 다음 위치 유효성 확인 (배열 범위 내 & 미방문)
if (nextX < 0 || nextX >= M || nextY < 0 || nextY >= N || visited[nextY][nextX]) {
// 유효하지 않다면 방향 전환(dir = (dir + 1) % 4) 후 재시도
dir = (dir + 1) % 4;
nextX = x + dx[dir];
nextY = y + dy[dir];
}
// 유효하다면 다음 위치로 이동
x = nextX;
y = nextY;
}
}
}
▶ 시간 복잡도 : O(NxM)
행렬 변환
: 행렬 변환은 데이터를 재구성하거나 변형하여 문제를 해결하는 데 사용됨
예를 들어, 겡미 개발에서는 3D 객체의 회전과 이동, 이미지 처리 시에는 사진의 회전과 뒤집기를 구현할 때 활용
public static int[][] transpose(int[][] matrix) {
int n = matrix.length; // 행의 개수
int m = matrix[0].length; // 열의 개수
// 행과 열의 크기를 바꿔서 새로운 배열 생성
int[][] result = new int[m][n];
// 모든 원소를 순회하며 위치 변환
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
result[j][i] = matrix[i][j];
}
}
return result;
}
90도 회전
- 행렬 인덱스 재배치: (i,j) → (j, N-1-i)
180도 회전
- 행렬 인덱스 재배치: (i,j) → (N-1-i, M-1-j)
270도 회전
- 행렬 인덱스 재배치: (i,j) → (M-1-j, i)
기억하기 위한 Tip!
- 90도씩 회전할때 i,j의 위치는 계속 바뀝니다.
- 첫번째 인덱스는 최대 인덱스에서 빼서 두번째 자리고 가고
- 두번째 인덱스는 그대로 첫번째 자리로 갑니다.
▼ 구현 코드
// 90도 회전 (직사각형 행렬)
public static int[][] rotate90(int[][] matrix) {
int N = matrix.length; // 행의 개수
int M = matrix[0].length; // 열의 개수
int[][] result = new int[M][N]; // 결과 배열의 크기가 바뀜
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
result[j][N-1-i] = matrix[i][j];
}
}
return result;
}
// 180도 회전 (직사각형 행렬)
public static int[][] rotate180(int[][] matrix) {
int N = matrix.length;
int M = matrix[0].length;
int[][] result = new int[N][M]; // 원래 크기 유지
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
result[N-1-i][M-1-j] = matrix[i][j];
}
}
return result;
}
// 270도 회전 (직사각형 행렬)
public static int[][] rotate270(int[][] matrix) {
int N = matrix.length;
int M = matrix[0].length;
int[][] result = new int[M][N]; // 결과 배열의 크기가 바뀜
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
result[M-1-j][i] = matrix[i][j];
}
}
return result;
}
