leetcode: 01 Matrix

방법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;
	}
}