NumberOfIsland_ DFS

Question

void merge(char[][] grid, int i, int j) {

// System.out.println("==merge===== i: " + i + " y: " + j);

// if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1')

// return;

// grid[i][j] = 'X';

// for(int[] dir: dirs) {

// merge(grid, i+dir[0], j+dir[1]);

// }

//

// merge(grid, i - 1, j);

// merge(grid, i + 1, j);

// merge(grid, i, j + 1);

// merge(grid, i, j - 1);

// }

NumberOfIsland_ DFS문제에서

이부분이 이해가안됩니다 특히 merge(grid,i+dir[0],dir[1]+j)

가 여러방향 훑는거라는 느낌은 들었는데 왜 인덱스 0과 1인지 과정이 궁금해서 질문남깁니다!

Answer

안녕하세요. 답변이 늦어 죄송합니다.

dfs는 정말 많이 물어보는 개념이죠 . 거의 외우다시피 하셔야하겠죠.

1) 질문주신

이부분이 이해가안됩니다 특히 merge(grid,i+dir[0],dir[1]+j) 가 여러방향 훑는거라는 느낌은 들었는데 왜 인덱스 0과 1인지 과정이 궁금해서 질문남깁니다!

merge(grid, i-1, j);

merge(grid, i+1, j);

merge(grid, i, j+1);

merge(grid, i, j-1);

와

for(int[] dir: dirs) {

merge(grid, i+dir[0], j+dir[1]);

}

은 같은 개념입니다.

즉 (0,0) 좌표를 사방으로 돌리기 시작하면

int[][] dirs= {{0,1},{0,-1},{1,0},{-1,0}}; 에서

int[] dir {0,1}을 만나면 (0,0) -> (0,1) 이 되고

int[] dir {0,-1}을 만나면 (0,0) -> (0,-1) 이 되고

int[] dir {1,0}을 만나면 (0,0) -> (1,0) 이 되고

int[] dir {-1,0}을 만나면 (0,0) -> (-1,0) 이 되고

이렇게 사방으로 체크하는 의미입니다.