1️⃣ 고쳐서 Accepted된(성공) 코드
처음에 내가 제출한 코드는 2️⃣였고 시간 초과로 실패했다.
그 후 문제점을 파악하고 고쳐서 낸 코드는 다음과 같다.
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
boolean[][] visited = new boolean[m][n];
int[][] res = new int[m][n];
Queue<Position> queue = new LinkedList<>();
// 상하좌우
int[] dy = {-1, 1, 0, 0};
int[] dx = {0, 0, -1, 1};
for (int y=0; y<m; y++){
for (int x=0; x<n; x++) {
if (mat[y][x] == 0) {
res[y][x] = 0;
visited[y][x] = true;
queue.add(new Position(y, x));
}
}
}
int dist = 0;
while (!queue.isEmpty()) {
int q_size = queue.size();
dist += 1;
for (int i= 0 ; i<q_size; i++) {
Position cur = queue.poll();
for (int j = 0; j<4; j++) {
int ny = cur.y + dy[j];
int nx = cur.x + dx[j];
if (ny<0 || ny >= m || nx<0 || nx >=n) continue;
if (visited[ny][nx] == true) continue;
res[ny][nx] = dist;
visited[ny][nx] = true;
queue.add(new Position(ny, nx));
}
}
}
return res;
}
class Position {
int y, x;
Position(int y, int x) {
this.y = y;
this.x = x;
}
}
}한 번만 BFS를 돌리는 구조이다. 모든 0을 시작점으로 큐에 담고 바깥으로 파동처럼 퍼뜨리면 각 1의 최단 거리가 한 번에 채워진다. (멀티 소스 BFS)
시간복잡도 : O(m*n) (각 칸을 최대 한번만 방문하므로)
🔹 같은 로직인 다른 코드
GPT가 제안한 코드이다. 개선된 부분이 많다.
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length, n = mat[0].length;
int[][] dist = new int[m][n];
// boolean[][] visited = new boolean[m][n]; //🟣
Deque<int[]> q = new ArrayDeque<>(); // 🟠
// 1) 모든 0을 큐에 넣고 방문 처리, 1은 일단 큰 값으로 채움
for (int y = 0; y < m; y++) {
for (int x = 0; x < n; x++) {
if (mat[y][x] == 0) {
dist[y][x] = 0;
// visited[y][x] = true; // 🟣
q.add(new int[]{y, x}); // 🟢
} else {
dist[y][x] = Integer.MAX_VALUE; // 🔵
}
}
}
int[] dy = {1, -1, 0, 0};
int[] dx = {0, 0, 1, -1};
// 2) 다중 시작점 BFS
while (!q.isEmpty()) {
int[] cur = q.poll();
int cy = cur[0], cx = cur[1];
for (int k = 0; k < 4; k++) {
int ny = cy + dy[k], nx = cx + dx[k];
if (ny < 0 || ny >= m || nx < 0 || nx >= n) continue;
// 더 짧은 거리로 갱신되면 큐에 푸시
if (dist[ny][nx] > dist[cy][cx] + 1) { //🟣
dist[ny][nx] = dist[cy][cx] + 1;
// visited 없이도 dist 갱신 여부로 방문 판단 가능. 🟣
// 더 짧은 거리로 갱신되지 않는 칸은 큐에 넣지 않는다.
q.add(new int[]{ny, nx});
}
}
}
return dist;
}
}▫️ 위 코드와 1️⃣ 코드의 차이점
-
(y, x) 좌표를 Position 클래스의 객체로 저장하는 게 아니라 일차원 int배열을 만들어 저장함. 큐도 이 int배열을 저장하도록 선언됨. 🟢
-
결과로 리턴할 dist배열에서 0이 아닌 cell은 Integer.MAX_VALUE을 활용하여 큰 값으로 채움. 기존의 경우에 int배열을 만들면 0으로 자동 초기화되기 때문에 mat에서 값이 1인 cell도 dist의 같은 위치 cell 값이 0이 되었었음. 🔵
-
🟣 비교 매커니즘이 다르다! (기존 : visited의 flag로) 설명은 주석에
-
큐를 LinkedList가 아닌 ArrayDeque로 구현하였다. 🟠
Linked List vs ArrayDeque
💫 Deque(덱/데크)란?
Double Ended Queue. 즉, 앞과 뒤 양쪽에서 삽입, 삭제가 모두 가능한 큐.
그러므로 스택과 큐를 모두 흉내낼 수 있는 자료 구조.
사용 예 : 양방향 BFS (앞뒤 모두에서 탐색 확장), 슬라이딩 윈도우 최적화(앞에서 빼고 뒤에 넣기), 덱 기반 스택/큐 혼합 구조)
ArrayDeque는 이름 그대로 배열(Array) 기반으로 구현된 원형 큐(circular buffer)이다.
내부적으로는 단일 배열 하나 + head, tail 인덱스만으로 동작한다. 동적으로 크기 조정도 가능하다.
그래서 ArrayDeque는 LinkedList에 비해
👍 앞뒤 삽입/삭제 offer/peek/poll이 아주 빠르고
👍 CPU 캐시 효율 높고(연속 메모리라서) 메모리 효율이 좋다.
다만, LinkedList와 달리
👎 null을 저장할 수 없다.
여기서는 ArrayDeque를 쓰는 것이 좋다.
참고로 LinkedList을 써야할 때는 다음과 같다.
- 리스트로서 중간 노드를 이터레이터로 가리킨 상태에서 자주 삽입/삭제할 때(큐가 아님)
- 요소로 null을 반드시 저장해야할 때시간복잡도는 이 코드 역시 O(m*n)
🔹 다른 방식인 다른 코드
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length, n = mat[0].length;
int[][] dist = new int[m][n];
int INF = 10_000_000;
// init
for (int y = 0; y < m; y++) {
for (int x = 0; x < n; x++) {
dist[y][x] = (mat[y][x] == 0) ? 0 : INF;
}
}
// pass 1: top-left to bottom-right
for (int y = 0; y < m; y++) {
for (int x = 0; x < n; x++) {
if (dist[y][x] == 0) continue;
if (y > 0) dist[y][x] = Math.min(dist[y][x], dist[y-1][x] + 1);
if (x > 0) dist[y][x] = Math.min(dist[y][x], dist[y][x-1] + 1);
}
}
// pass 2: bottom-right to top-left
for (int y = m - 1; y >= 0; y--) {
for (int x = n - 1; x >= 0; x--) {
if (y + 1 < m) dist[y][x] = Math.min(dist[y][x], dist[y+1][x] + 1);
if (x + 1 < n) dist[y][x] = Math.min(dist[y][x], dist[y][x+1] + 1);
}
}
return dist;
}
}2-pass DP 방식.
두 방향으로 한번씩 훑으면서 이전 계산 결과를 이용하여 최솟값 갱신.
각 칸은 최대 두 번만 갱신되므로 시간복잡도 O(m*n)
2️⃣ 처음에 풀어서 낸 실패 코드
Time Limit Exceeded(시간 초과)로 실패
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int[][] res = new int[m][n];
for (int i=0 ; i < m ; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0) {
res[i][j] = 0;
continue;
}
res[i][j] = bfs(new Position(i, j, 0), m, n, mat);
}
}
return res;
}
static int bfs(Position one, int m, int n, int[][] mat) {
boolean[][] visited = new boolean[m][n];
Queue<Position> queue = new LinkedList<>();
queue.add(one);
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
while (!queue.isEmpty()) {
Position cur = queue.poll();
visited[cur.y][cur.x] = true;
if (mat[cur.y][cur.x] == 0) {
return cur.dist;
}
for (int i=0; i<4; i++) {
int ny = cur.y + dy[i];
int nx = cur.x + dx[i];
if (ny<0 || ny >= m || nx<0 || nx >= n)
continue;
if (visited[ny][nx] == true)
continue;
queue.add(new Position(ny, nx, cur.dist+1));
}
}
return -1;
}
static class Position {
int y, x, dist;
public Position(int y, int x, int dist) {
this.y = y;
this.x = x;
this.dist = dist;
}
}
}- 시간초과 이유 : 각각의 1을 중심으로 가장 가까운 0을 계산하다 보면 각 1마다 bfs를 돌리게 된다.
다시 말해, 각 1셀마다 BFS를 새로 돌리는 구조이니 O((mn)^2)이다.
문제의 제약 조건에서1 <= m * n <= 10^4이었으므로 시간 초과가 난다.
BFS 생초보로서 이 문제를 통해 BFS를 어떻게 활용해야 할지에 대해 더 확실히 감을 잡을 수 있었다. 그리고 BFS가 아닌 다른 방식으로 푸는 아이디어(2-pass DP)가 참신하게 다가왔다.
