예제로 배우는 알고리즘 - 행렬

행렬 순회

 

예제 - LeetCode 36. Valid Sudoku

https://leetcode.com/problems/valid-sudoku/?envType=study-plan-v2&envId=top-interview-150

 

 

1. 문제 이해

• 채워진 칸(.이 아닌)에 대해 스도쿠 조건을 만족하는지 검사

 

2. 요구사항 분석

• 입력
  • board.length == 9
  • board[i].length == 9
  • board[i][j]는 1-9 사이의 숫자, 빈칸은 '.'
• 출력
  • 모든 채워진 칸이 조건을 만족하면 true, 아니면 false

 

 

3. 해결 아이디어

• 각 행, 열, 박스의 중복을 검사할 set 할당
• 해당 칸의 숫자를 set에 넣어가며 중복 검사, 중복이 있다면 불가능

 

4. 시간 복잡도 및 공간 복잡도 확인

 

• 시간 복잡도
  • 9 * 9의 고정 크기를 순회하므로 O(1)
• 공간 복잡도
  • 최대 9개 크기의 27개의 set을 사용하므로 O(1)

 

5. 구현

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // 1. 각 행, 열, 박스에 대한 숫자 기록용 Set 할당
        Set<Character>[] rows = new HashSet[9];
        Set<Character>[] cols = new HashSet[9];
        Set<Character>[] boxes = new HashSet[9];

        // 2. 각 Set 초기화
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashSet<>();
            cols[i] = new HashSet<>();
            boxes[i] = new HashSet<>();
        }

        // 3. 전체 보드를 순회하며 검사
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                char val = board[r][c]; // 현재 숫자
                if (val == '.') continue; // 빈칸은 검사 안함

                // 3-1) 3x3 박스 인덱스 계산
                int boxIndex = (r / 3) * 3 + (c / 3);

                // 3-2) 중복 검사 -> 이미 존재하면 조건에 어긋남
                if (rows[r].contains(val) || cols[c].contains(val) || boxes[boxIndex].contains(val)) {
                    return false;
                }

                // 3-3) 현재 숫자를 set에 기록
                rows[r].add(val);
                cols[c].add(val);
                boxes[boxIndex].add(val);
            }
        }

        return true;
    }
}

 

예제 - LeetCode 54. Spiral Matrix

https://leetcode.com/problems/spiral-matrix/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 이해

• 2차원 행렬을 시계 방향 나선형으로 배열을 순회

 

2. 요구사항 분석

• 입력
  • 1 <= matrix.length, matrix[i].lenght <= 10
  • -100 <= matrix[i][j] <= 100
• 출력
  • 조건 순서대로 정수를 나열한 리스트

 

 

3. 해결 아이디어

• 경계를 할당하고 왼 -> 오, 위 -> 아래, 오 -> 왼, 아래 -> 위 방향으로 순회
• 경계를 하나씩 줄여가며 반복

 

4. 시간 복잡도 및 공간 복잡도 확인

 

• 시간 복잡도
  • 행렬의 크기만큼 순회하므로 O(m * n)
• 공간 복잡도
  • 결과를 저장할 리스트를 사용하므로 O(m * n)

 

5. 구현

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        // 1. 결과를 저장할 리스트 및 경계 할당 
        List<Integer> result = new ArrayList<>();

        int top = 0;
        int bottom = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;

        // 2. 나선 순서대로 순회하며 경계를 하나씩 줄여가기
        while (top <= bottom && left <= right) {
            // 2-1) 왼 → 오
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            top++;

            // 2-2) 위 → 아래
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--;

            // 2-3) 오 → 왼
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }
                bottom--;
            }

            // 2-4) 아래 → 위
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }

        return result;
    }
}

 

행렬 변환

 

예제 - LeetCode 48. Rotate Image

https://leetcode.com/problems/rotate-image/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 이해

• 2차원 배열을 시계 방향으로 회전, 단 새로운 배열 없이 직접 수정

 

2. 요구사항 분석

• 입력
  • n = matrix.length = matrix[i].length
  • 1 <= n <= 20
  • -1,000 <= matrix[i][j] <= 1,000
• 출력
  • 없음, 주어진 행렬을 변환

 

 

3. 해결 아이디어

• 정사각형 행렬에서 전치(행렬의 행과 열을 바꿈) + 행 뒤집기(좌우반전) -> 시계방향 90도 회전임을 이용

다음 뒤집기 전략도 기억해두면 편리

• 전치 + 열 뒤집기(상하반전) -> 반시계방향 90도 회전
• 행 뒤집기 + 열 뒤집기 -> 180도 회전

 

4. 시간 복잡도 및 공간 복잡도 확인

 

• 시간 복잡도
  • 전치, 뒤집기 각각 행렬을 순회하므로 O(n * n)
• 공간 복잡도
  • 추가 행렬을 사용하지 않으므로 O(1)

 

5. 구현

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // 1. 전치 → 대각선을 기준으로 뒤집기
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // 2. 각 행을 좌우 반전
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}

 

예제 - LeetCode 73. Set Matrix Zeroes

https://leetcode.com/problems/set-matrix-zeroes/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 이해

• 2차원 배열에서 어떤 요소가 0이라면 해당 행과 열의 모든 요소를 0으로 변경, 단 추가 행렬 없이 처리

 

2. 요구사항 분석

• 입력
  
  • 1 <= matrix.length = matrix[i].length <= 200
  • matrix[i][j]는 int 범위
• 출력
  • 없음, 주어진 행렬을 변환

 

 

3. 해결 아이디어

• 첫 행/열을 해당 행/열을 0으로 바꿔야하는지에 대한 마커로 표시
• 첫 행/열에  0이 포함되었는지 기록 -> 마지막에 첫 행/열 부분 마무리 하기 위함
• 그 이외 셀을 확인하며 0으로 바꿔야하는 행/열에 0으로 마커 표시
• 마커를 기준으로 해당 행/열을 모두 0으로 변경
• 첫 행/열을 기록에 맞춰 0으로 마무리

 

4. 시간 복잡도 및 공간 복잡도 확인

 

• 시간 복잡도
  • 전체 행렬을 한 번 순회하므로 O(m * n)
• 공간 복잡도
  • 추가 행렬을 사용하지 않으므로 O(1)

 

5. 구현

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean firstRowZero = false, firstColZero = false;

        // 1. 첫 행/열이 0이 포함되어 있는지 별도로 기록
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) firstColZero = true;
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) firstRowZero = true;
        }

        // 2. 나머지 셀 검사 → 첫 행/열을 마커로 사용
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // 3. 마커를 참고해서 0으로 세팅
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // 4. 첫 행/열 마무리 처리
        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }

        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }
}

 

예제 - LeetCode 289. Game of Life

https://leetcode.com/problems/game-of-life/description/?envType=study-plan-v2&envId=top-interview-150

1. 문제 이해

• 2차원 배열에서 각 셀은 1(생존), 0(죽음)으로 표현되고 다음 규칙으로 동시에 갱신됨
  • 살아있는 셀 주변 1개 이하 살아있는 이웃이 있다면 죽음
  • 살아있는 셀 주변 2개 또는 3개 살아있는 이웃이 있다면 생존
  • 살아있는 셀 주변 3개 초과의 살아있는 이웃이 있다면 죽음
  • 죽어있는 셀 주변 3개의 살아있는 이웃이 있다면 생존
  • 각 셀의 주변은 8방향을 의미

 

2. 요구사항 분석

• 입력
  
  • 1 <= board.length = board[i].length <= 25
  • board[i][j]는 0 또는 1
• 출력
  • 없음, 주어진 행렬을 변환

 

 

3. 해결 아이디어

• 이전 상태와 이후 상태를 구분하기 위해 -2(죽을 셀), -1(살아날 셀) 마킹을 추가로 사용

 

4. 시간 복잡도 및 공간 복잡도 확인

 

• 시간 복잡도
  • 전체 행렬을 한 번 순회하고 각 8방향 탐색하므로(m*n*8) O(m * n)
• 공간 복잡도
  • 추가 행렬을 사용하지 않으므로 O(1)

 

5. 구현

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;

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

        // 1. 각각 셀의 상태를 마킹
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int liveNeighbors = 0;

                for (int[] dir : dirs) {
                    int ni = i + dir[0], nj = j + dir[1];
                    if (0 <= ni && ni < m && 0 <= nj && nj < n) {
                        // 1 or -2는 이전 상태가 살아 있었던 것
                        if (board[ni][nj] == 1 || board[ni][nj] == -2) {
                            liveNeighbors++;
                        }
                    }
                }

                // 살아 있는 셀
                if (board[i][j] == 1) {
                    if (liveNeighbors < 2 || liveNeighbors > 3) {
                        board[i][j] = -2; // 살았는데 죽을 셀 (1 → 0)
                    }
                }
                // 죽어 있는 셀
                else {
                    if (liveNeighbors == 3) {
                        board[i][j] = -1; // 죽었는데 살아날 셀 (0 → 1)
                    }
                }
            }
        }

        // 2. 마킹을 실제 값으로 변환(-2 -> 0, -1 -> 1)
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == -2) board[i][j] = 0;
                else if (board[i][j] == -1) board[i][j] = 1;
            }
        }
    }
}

 

만일 board가 무한하다면 2차원 배열을 사용할 수 없으므로, Set으로 살아있는 셀을 관리하고, Map으로 셀의 주변 8칸의 이웃 수를 세는 방법을 활용해 Set을 갱신하는 방법으로 구현 가능

 

의사코드

Set<Pair> alive = new HashSet<>();  // 현재 살아 있는 셀

Map<Pair, Integer> neighborCount = new HashMap<>();

// 1. 살아 있는 셀의 주변 8칸의 이웃 수를 세기
for (Pair cell : alive) {
    for (int[] dir : directions) {
        Pair neighbor = new Pair(cell.x + dir[0], cell.y + dir[1]);
        neighborCount.put(neighbor, neighborCount.getOrDefault(neighbor, 0) + 1);
    }
}

// 2. 다음 세대의 살아 있는 셀 결정
Set<Pair> nextAlive = new HashSet<>();
for (Map.Entry<Pair, Integer> entry : neighborCount.entrySet()) {
    Pair cell = entry.getKey();
    int count = entry.getValue();

    if (alive.contains(cell)) {
        if (count == 2 || count == 3) nextAlive.add(cell); // 생존
    } else {
        if (count == 3) nextAlive.add(cell); // 새로 살아남
    }
}

// 3. 상태 갱신
alive = nextAlive;