728x90
반응형
728x90
[NeetCode-LeetCode] Pacific Atlantic Water Flow - Medium
접근
- bfs
- dfs
풀이
태평양과 대서양으로 물이 흘러갈 수 있는지 확인하는 문제이다. 문제를 읽었을 때 이해가 빠르게 되는 문제는 아니었다. 좌표에는 물의 깊이 값이 들어있고 특정 좌표에서 물은 상하좌우로 흐를 수 있고 좌표의 다음 칸이 기존 좌표의 값과 동일하거나 더 작아야 흘러갈 수 있다는 그런 내용인 거 같았다. 결론은 특정 좌표에 물이 두 바다에 모두 도달이 가능한 지 체크하는 문제인 것 같았다.
그렇다면 양쪽 바다에서 시작해 모든 좌표를 체크하고 도달 가능한 두 좌표가 겹치는 부분을 찾으면 될 것이다.
private static final int[] dx = {-1, 1, 0, 0};
private static final int[] dy = {0, 0, -1, 1};
public List<List<Integer>> pacificAtlantic(int[][] heights) {
List<List<Integer>> result = new ArrayList<>();
if (heights == null || heights.length == 0 || heights[0].length == 0) {
return result;
}
int m = heights.length, n = heights[0].length;
boolean[][] pacificCheck = new boolean[m][n];
boolean[][] atlanticCheck = new boolean[m][n];
Queue<int[]> pacificQueue = new LinkedList<>();
Queue<int[]> atlanticQueue = new LinkedList<>();
for (int i = 0; i < m; i++) {
pacificQueue.offer(new int[]{i, 0});
pacificCheck[i][0] = true;
}
for (int i = 0; i < n; i++) {
pacificQueue.offer(new int[]{0, i});
pacificCheck[0][i] = true;
}
for (int i = 0; i < m; i++) {
atlanticQueue.offer(new int[]{i, n - 1});
atlanticCheck[i][n - 1] = true;
}
for (int i = 0; i < n; i++) {
atlanticQueue.offer(new int[]{m - 1, i});
atlanticCheck[m - 1][i] = true;
}양쪽 바다에 닿는 부분에서 시작할 예정이기 때문에 바다에 닿는 좌표들을 각 큐에 나눠서 담아준다. bfs를 통해 풀 거 기 때문에 큐를 사용해 주었고 대서양과 태평양을 나눠서 진행해 준 뒤 결과를 병합하여 모두 만족하는 부분을 구하게 된다.
bfs(heights, pacificQueue, pacificCheck, m, n);
bfs(heights, atlanticQueue, atlanticCheck, m, n);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacificCheck[i][j] && atlanticCheck[i][j]) {
result.add(Arrays.asList(i, j));
}
}
}
return result;두 바다와 닿는 부분을 bfs를 통해 체크하고 만들어진 결과를 통해 모두 만족하는 부분을 찾는다.
private void bfs(int[][] heights, Queue<int[]> queue, boolean[][] check, int m, int n) {
while (!queue.isEmpty()) {
int[] xy = queue.poll();
int x = xy[0];
int y = xy[1];
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !check[nx][ny]
&& heights[nx][ny] >= heights[x][y]) {
check[nx][ny] = true;
queue.offer(new int[]{nx, ny});
}
}
}
}bfs 코드이다. 각 좌표에서 상하 좌우로 탐색을 진행해주고 방문이 가능한 곳은 큐에 넣어 다음 좌표로 정하고 방문 체크를 수행해 준다. 기본적으로 물이 흐르기 위해선 다음 좌표의 값이 현재 좌표보다 크거나 같아야 하기에 만족한다면 큐에 넣는다.
dfs
특정 경로를 탐색하는 것이 아닌 단순히 방문 가능한지 체크를 하는 문제이기 때문에 dfs를 사용해서도 풀 수 있다. dfs를 사용하는 경우 재귀를 통해 풀어지기 때문에 큐를 사용한 bfs 보다 빠르게 해결이 가능하기도 하다. dfs 코드는 풀어진 제일 성능이 빨랐던 코드가 dfs였기 때문에 해당 코드를 가져왔다.
private int[][] directions = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
private int ROWS, COLS;
private char[][] visited;
private List<List<Integer>> result;
public List<List<Integer>> pacificAtlantic(int[][] heights) {
result = new ArrayList<>();
ROWS = heights.length;
COLS = heights[0].length;
visited = new char[ROWS][COLS];
// Begin DFS from every cells in the border
// The cells touching atlantic are with
// lowest row and highest col
for (int i = 0; i < COLS; i++) {
dfs(heights, ROWS - 1, i, 'A');
}
for (int i = 0; i < ROWS; i++) {
dfs(heights, i, COLS - 1, 'A');
}
// The cells touching pacific are with
// highest row and lowest col
for (int i = 0; i < COLS; i++) {
dfs(heights, 0, i, 'P');
}
for (int i = 0; i < ROWS; i++) {
dfs(heights, i, 0, 'P');
}
return result;
}위의 bfs코드와 크게 다른 부분은 없다. 동일하게 바다와 닿이는 부분의 좌표에서 dfs를 시작하게 되는데 해당 코드에선 하나의 함수로 해결하기 위해 A, P를 통해 바다의 종류를 구분하고 있다.
private void dfs(int[][] grid, int row, int col, char fill) {
if (visited[row][col] == 'A' && fill == 'P') {
result.add(Arrays.asList(row, col));
}
visited[row][col] = fill;
for (int[] dir : directions) {
int x = row + dir[0], y = col + dir[1];
if (x < 0 || y < 0 || x > ROWS - 1 || y > COLS - 1)
continue;
if (grid[x][y] < grid[row][col] || visited[x][y] == fill)
continue;
dfs(grid, x, y, fill);
}
}dfs 코드이다. 위의 메인 코드에서 먼저 A 바다, 대서양에 대해서 dfs를 실행해주게 되는데 해당 부분은 visited에 대서양과 닿는 좌표를 체크하기 위해 실행된다. 이 문제의 결과로는 양쪽 바다에 모두 닿이는 좌표를 구해야 한다. 그러므로 먼저 대서양과 닿이는 부분을 체크 해놓고 아래의 P, 태평양과 닿이는 부분을 체크하면서 이전 대서양 dfs에서 구해놨던 visited 배열을 참고해 공통적으로 만족하는 좌표만 추가하게 된다. 결국 fill의 값이 'A'로 dfs가 수행될 때는 대서양과 닿이는 좌표 체크만을 위한 것이고 아래의 fill 값이 'P'로 dfs가 수행될 때 result에 대한 실제 삽입이 일어나게 되는 것이다.
전체 코드
bfs
class Solution {
private static final int[] dx = {-1, 1, 0, 0};
private static final int[] dy = {0, 0, -1, 1};
public List<List<Integer>> pacificAtlantic(int[][] heights) {
List<List<Integer>> result = new ArrayList<>();
if (heights == null || heights.length == 0 || heights[0].length == 0) {
return result;
}
int m = heights.length, n = heights[0].length;
boolean[][] pacificCheck = new boolean[m][n];
boolean[][] atlanticCheck = new boolean[m][n];
Queue<int[]> pacificQueue = new LinkedList<>();
Queue<int[]> atlanticQueue = new LinkedList<>();
for (int i = 0; i < m; i++) {
pacificQueue.offer(new int[]{i, 0});
pacificCheck[i][0] = true;
}
for (int i = 0; i < n; i++) {
pacificQueue.offer(new int[]{0, i});
pacificCheck[0][i] = true;
}
for (int i = 0; i < m; i++) {
atlanticQueue.offer(new int[]{i, n - 1});
atlanticCheck[i][n - 1] = true;
}
for (int i = 0; i < n; i++) {
atlanticQueue.offer(new int[]{m - 1, i});
atlanticCheck[m - 1][i] = true;
}
bfs(heights, pacificQueue, pacificCheck, m, n);
bfs(heights, atlanticQueue, atlanticCheck, m, n);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacificCheck[i][j] && atlanticCheck[i][j]) {
result.add(Arrays.asList(i, j));
}
}
}
return result;
}
private void bfs(int[][] heights, Queue<int[]> queue, boolean[][] check, int m, int n) {
while (!queue.isEmpty()) {
int[] xy = queue.poll();
int x = xy[0];
int y = xy[1];
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !check[nx][ny]
&& heights[nx][ny] >= heights[x][y]) {
check[nx][ny] = true;
queue.offer(new int[]{nx, ny});
}
}
}
}
}
dfs
class Solution {
private int[][] directions = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
private int ROWS, COLS;
private char[][] visited;
private List<List<Integer>> result;
public List<List<Integer>> pacificAtlantic(int[][] heights) {
result = new ArrayList<>();
ROWS = heights.length;
COLS = heights[0].length;
visited = new char[ROWS][COLS];
// Begin DFS from every cells in the border
// The cells touching atlantic are with
// lowest row and highest col
for (int i = 0; i < COLS; i++) {
dfs(heights, ROWS - 1, i, 'A');
}
for (int i = 0; i < ROWS; i++) {
dfs(heights, i, COLS - 1, 'A');
}
// The cells touching pacific are with
// highest row and lowest col
for (int i = 0; i < COLS; i++) {
dfs(heights, 0, i, 'P');
}
for (int i = 0; i < ROWS; i++) {
dfs(heights, i, 0, 'P');
}
return result;
}
private void dfs(int[][] grid, int row, int col, char fill) {
if (visited[row][col] == 'A' && fill == 'P') {
result.add(Arrays.asList(row, col));
}
visited[row][col] = fill;
for (int[] dir : directions) {
int x = row + dir[0], y = col + dir[1];
if (x < 0 || y < 0 || x > ROWS - 1 || y > COLS - 1)
continue;
if (grid[x][y] < grid[row][col] || visited[x][y] == fill)
continue;
dfs(grid, x, y, fill);
}
}
}728x90
'알고리즘 > 코딩테스트-NeetCode' 카테고리의 다른 글
| [NeetCode-LeetCode] House Robber II JAVA (0) | 2025.01.07 |
|---|---|
| [NeetCode-LeetCode] House Robber JAVA (0) | 2025.01.06 |
| [NeetCode-LeetCode] Design Add and Search Words Data Structure JAVA (0) | 2025.01.02 |
| [NeetCode-LeetCode] Subtree of Another Tree JAVA (0) | 2025.01.01 |
| [NeetCode-LeetCode] Find Minimum in Rotated Sorted Array JAVA (0) | 2024.12.31 |