[LeetCode] 73. Set Matrix Zeroes 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Set Matrix Zeroes

---

 

문제 요약 (Set Matrix Zeroes)

m x n 행렬이 주어질 때, 어떤 원소가 0이라면, 그 원소가 속한 행 전체와 열 전체를 0으로 설정해야 한다.
⚠️ 단, 추가 배열 없이(in-place) 해결해야 한다.

 

문제링크: https://leetcode.com/problems/set-matrix-zeroes

 

---

🤔 처음 떠올린 아이디어
처음 문제를 봤을 때는 이렇게 생각했다.

0을 발견하면, 그것을 queue와 같은 곳에 저장하고,
하나씩 꺼내면서 그 원소 위치의 행이랑 열을 전부 0으로 만들면 되지 않을까?

 

그래서 자연스럽게 떠올린 방식은:

• 0의 위치를 Queue에 저장
• 하나씩 꺼내면서 위 / 아래 / 왼쪽 / 오른쪽으로 전부 0 처리

즉, 0을 퍼뜨리는 방식이었다.

하지만 곧 문제가 보였다.

• 방금 0으로 만든 값이
• 다시 새로운 0으로 인식되면서
• 불필요한 중복 처리가 계속 발생

---

💡 핵심 깨달음: 이건 ‘전파’가 아니라 ‘기억’의 문제

이 문제에서 중요한 건 딱 하나다.

어디에 0이 있었는가?

 

• 0이 언제 처리됐는지는 중요하지 않다
• 0이 어떤 행 / 어떤 열에 있었는지만 기억하면 된다.

 

즉, 구조는 이렇게 바뀐다.

• 1단계: 0이 있었던 행과 열을 기록
• 2단계: 기록된 행과 열을 한 번에 0 처리

 

이 문제는
👉 마킹(marking) 문제다.

---

🤔 그럼 행 / 열 정보는 어디에 저장하지?

가장 직관적인 방법은 이거다.

boolean[] zeroRow;
boolean[] zeroCol;

 

하지만 문제 조건은 in-place. 👉 즉, 추가 공간을 쓰면 안 된다.

그래서 자연스럽게 다음 질문이 나온다.

“이 정보를… 행렬 자체에 저장할 수 없을까?”

---

 

💡 관찰: 행렬에는 이미 ‘대표 칸’이 있다

행렬을 보면 이미 이런 구조가 존재한다.

• i번째 행을 대표하는 칸 → matrix[i][0]
• j번째 열을 대표하는 칸 → matrix[0][j]

 

그래서 아이디어가 이렇게 바뀐다.

어차피 0으로 만들 행과 열이라면
그 대표 칸을 마커로 써도 되지 않을까?

 

👉 첫 행과 첫 열을 마커로 사용하자

---

⚠️ 단 하나의 함정: 첫 행 / 첫 열 자체는?

문제가 하나 생긴다. 

첫 행이나 첫 열에 원래 0이 있었다면?

• 마커 때문에 0이 된 건지
• 원래부터 0이었는지

구분이 안 된다.

그래서 이 둘은 따로 기억해야 한다.

boolean firstRowZero;
boolean firstColZero;

---

🧠 전체 풀이 흐름 정리

1. 첫 행 / 첫 열에 0이 있는지 확인 (firstRowZero, firstColZero)
2. 나머지 영역을 순회하며 마킹
   1. matrix[i][0] = 0; // i번째 행 마커
   2. matrix[0][j] = 0; // j번째 열 마커
3. 마커를 기준으로 내부를 0 처리
4. 마지막에 첫 행 / 첫 열 처리 

---

 

코드 (Java)

class Solution {
  public void setZeroes(int[][] matrix) {
    int row = matrix.length;
    int col = matrix[0].length;

    boolean firstRowZero = false;
    boolean firstColZero = false;

    // 첫 열 확인
    for (int i = 0; i < row; i++) {
      if (matrix[i][0] == 0) {
        firstColZero = true;
        break;
      }
    }

    // 첫 행 확인
    for (int j = 0; j < col; j++) {
      if (matrix[0][j] == 0) {
        firstRowZero = true;
        break;
      }
    }

    // 마킹
    for (int i = 1; i < row; i++) {
      for (int j = 1; j < col; j++) {
        if (matrix[i][j] == 0) {
          matrix[i][0] = 0;
          matrix[0][j] = 0;
        }
      }
    }

    // 내부 0 처리
    for (int i = 1; i < row; i++) {
      for (int j = 1; j < col; j++) {
        if (matrix[i][0] == 0 || matrix[0][j] == 0) {
          matrix[i][j] = 0;
        }
      }
    }

    // 첫 열
    if (firstColZero) {
      for (int i = 0; i < row; i++) {
        matrix[i][0] = 0;
      }
    }

    // 첫 행
    if (firstRowZero) {
      for (int j = 0; j < col; j++) {
        matrix[0][j] = 0;
      }
    }
  }
}

 

 

📈 Time / Space Complexity

• 시간: 모든 칸을 상수 번 순회 → O(M × N)
• 공간: 추가 배열 없음 → O(1)

---

 

📝 이번 문제에서 얻은 깨달음

• 지금 바꾸지 말고, 기억했다가 나중에 바꿔라는 사고가 핵심
• in-place 문제는 👉 입력 공간을 메모리로 재활용할 수 있는지를 먼저 생각해야 한다
• 전파처럼 보여도, 사실은 마킹 문제일 수 있다.

---

 

💡 마킹(Marking) 문제란?

마킹 문제는

“지금 바로 바꾸지 말고,
나중에 바꿀 대상을 먼저 표시해두는 문제”

 

이 문제에서 0을 발견했을 때
즉시 행과 열을 0으로 만들면,
방금 만든 0이 새로운 조건이 되어
불필요한 처리가 계속 발생할 수 있다.

 

그래서 구조가 반드시 분리된다.

 

1️⃣ 대상 기록 (마킹)
2️⃣ 기록 기반으로 한 번에 반영

 

👉 값의 전파가 아니라, 대상의 기억이다.

 

---

 

🧠 마킹을 써야 하는 순간은 언제일까?

아래 중 2개 이상 보이면
👉 마킹 문제를 의심하자.

1️⃣ “하나라도 있으면 전부 바꿔라” 구조

• 특정 값이 있으면 그 주변 / 행 / 열 / 영역 전체가 바뀜 

2️⃣ 변경된 값이 다시 조건이 될 수 있을 때

• 방금 바꾼 값이 다음 판단에 영향을 준다
  👉 판단과 반영을 분리해야 한다

3️⃣ “in-place로 하라”는 조건

• 기억은 해야 하는데 저장소는 안 준다는 뜻
  👉 입력 자체를 재활용하라는 힌트

4️⃣ 시간 흐름이 중요하지 않을 때

• 언제 바뀌는지는 중요하지 않고 결과만 맞으면 된다
  👉 BFS ❌ / 마킹 ⭕

🔍 한 줄 판별법

“이거… 지금 바꾸면 안 되는 거 아니야?”

 

이 생각이 들면
👉 거의 확실히 마킹 문제