방법1 - 각 cell에서 1인 부분을 큐에 넣고 bfs를 통해 0까지의 최소 거리를 찾는다.
import java.util.*;
class Solution {
public static int dr[] = { 0, 0, 1, -1 };
public static int dc[] = { 1, -1, 0, 0 };
public int[][] updateMatrix(int[][] matrix) {
Queue<Position> queue = new LinkedList<Position>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] != 0) {
queue.add(new Position(i, j, 0));
}
}
}
while (!queue.isEmpty()) {
Position now = queue.poll();
updateCell(now.row, now.col, matrix);
}
return matrix;
}
public void updateCell(int row, int col, int[][] matrix) {
Queue<Position> queue = new LinkedList<Position>();
queue.add(new Position(row, col, 0));
while (!queue.isEmpty()) {
Position now = queue.poll();
if (matrix[now.row][now.col] == 0) {
matrix[row][col] = now.value;
return;
}
for (int i = 0; i < 4; i++) {
int newRow = now.row + dr[i];
int newCol = now.col + dc[i];
if (isBoundary(newRow, newCol, matrix)) {
queue.add(new Position(newRow, newCol, now.value + 1));
}
}
}
}
public boolean isBoundary(int row, int col, int[][] matrix) {
if (row < 0 || row >= matrix.length) {
return false;
}
if (col < 0 || col >= matrix[row].length) {
return false;
}
return true;
}
public void printMatrix(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
}
class Position {
int row, col, value;
public Position(int row, int col, int value) {
this.row = row;
this.col = col;
this.value = value;
}
}
방법2 - 어차피 matrix에 거리를 계속 업데이트 하고 있는데 이 것을 이용해서 다음 값을 구할 수 없을까? => DP
class Solution {
public int[][] updateMatrix(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
int[][] dp = matrix;
int INF = 10000;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 1) {
dp[i][j] = INF;
}
}
}
for (int i = 1; i < n; i++) {
dp[i][0] = Math.min(dp[i][0], dp[i - 1][0] + 1);
}
for (int i = 1; i < m; i++) {
dp[0][i] = Math.min(dp[0][i], dp[0][i - 1] + 1);
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
dp[i][j] = Math.min(dp[i][j], Math.min(dp[i][j - 1], dp[i - 1][j]) + 1);
}
}
for (int i = n - 2; i >= 0; i--) {
dp[i][m - 1] = Math.min(dp[i + 1][m - 1] + 1, dp[i][m - 1]);
}
for (int i = m - 2; i >= 0; i--) {
dp[n - 1][i] = Math.min(dp[n - 1][i + 1] + 1, dp[n - 1][i]);
}
for (int i = n - 2; i >= 0; i--) {
for (int j = m - 2; j >= 0; j--) {
dp[i][j] = Math.min(dp[i][j], Math.min(dp[i][j + 1], dp[i + 1][j]) + 1);
}
}
return dp;
}
}'알고리즘 공부 > leetcode' 카테고리의 다른 글
| leetcode: Maximum Frequency Stack (0) | 2021.01.23 |
|---|---|
| leetcode: Range Sum Query - Mutable (0) | 2021.01.10 |
| leetcode: Number of Islands (0) | 2021.01.07 |
| leetcode: Trapping Rain Water (0) | 2020.12.27 |
| leetcode: Median of two sorted Arrays (0) | 2020.12.26 |
