-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
NumberOfIsland_Bfs
20.06.01 18:41 작성 조회수 117
1
bfs 풀이법에서
//package Graph_DFS_BFS;
//
//import java.util.LinkedList;
//import java.util.Queue;
//
////dfs 스택 bfs 바베큐 -> 큐
//public class NumberOfIsland_BFS {
// public static void main(String[] args) {
//
// char[][] grid = { { '1', '1', '0', '0', '1' }, { '1', '1', '0', '0', '0' }, { '0', '0', '0', '0', '0' },
// { '0', '0', '0', '1', '1' } };
//
// NumberOfIsland_BFS a = new NumberOfIsland_BFS();
// System.out.println(a.numberOfIsland(grid));
//
// }
//
// int numberOfIsland(char[][] grid) {
// if (grid == null || grid.length == 0)
// return 0;
// int count = 0;
//
// for (int i = 0; i < grid.length; i++) {
// for (int j = 0; j < grid[0].length; j++) {
// if (grid[i][j] == '1') {
// count++;
// bfs(grid, i, j);
// }
// }
// }
//
// return count;
// }
//
// // 사방으로 체크하기위한 좌표값 만듬
// int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
//
// public void bfs(char[][] grid, int x, int y) {
// Queue<int[]> queue = new LinkedList<int[]>();
// queue.offer(new int[] { x, y }); // 지금 0,0을 넣은거임
// while (!queue.isEmpty()) {
// int size = queue.size();
// int[] point = queue.poll();
// for (int i = 0; i < size; i++) {
// for (int[] dir : dirs) {
// int x1 = point[0] + dir[0];
// int y1 = point[1] + dir[1];
// if (x1 >= 0 && y1 >= 0 && x1 < grid.length && y1 < grid[0].length && grid[x1][y1] == '1') {
// grid[x1][y1] = '0';
// queue.offer(new int[] { x1, y1 });
// }
// }
// }
// }
//
// }
//
//}
마지막에
for (int i = 0; i < size; i++) {
// for (int[] dir : dirs) {
// int x1 = point[0] + dir[0];
// int y1 = point[1] + dir[1];
// if (x1 >= 0 && y1 >= 0 && x1 < grid.length && y1 < grid[0].length && grid[x1][y1] == '1') {
// grid[x1][y1] = '0';
// queue.offer(new int[] { x1, y1 });
// }
이부분의 동작원리와 코딩이 이해가안됩니다 ㅠㅠ 어떻게 훑고 가는거지..
답변을 작성해보세요.
1
푸샵맨 코딩스터디
지식공유자2020.06.04
이 문제는 강의를 잘 보시고, 계속해서 디버그로 누르면서 체크해 보세요.
카카오 블라인드 테스트에서 무조건 bfs, dfs가 나오더라구요.
문제를 풀어보겠습니다.
질문 주신
"이부분의 동작원리와 코딩이 이해가안됩니다 ㅠㅠ 어떻게 훑고 가는거지.."
이 문제는 bfs 문제로 queue를 이용해서 1의 값을 찾아내서 좌표에 사방으로 한칸씩 이동하면서 체크하고,
0을 만나면 끝나버리게됩니다.
결국에 1로 인접한 섬을 구하는건데 , 문제의 답은 3입니다. 1로 이루어진 섬이 3개라는거죠
결국에 옆에 한칸씩 이동한다-> 그게 큐로 이용하게 끔 만들어진 문제
for(int[] dir: dirs) {
int x1= point[0]+dir[0];
int y1 = point[1]+dir[1];
(0,0)이 기준값이라면 사방으로 더해줍니다. {{-1,0},{1,0},{0,1},{0,-1}};
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) 이 되고
이렇게 사방으로 체크하는 의미입니다.
if(x1>=0 && y1>=0 && x1< grid.length && y1< grid[0].length && grid[x1][y1]=='1') {
x1>=0 && y1>=0 , 우리가 구하는 값은 양의 좌표값이 나와야겠죠. 양의 좌표값 체크하는 부분
x1< grid.length && y1< grid[0].length, 4*3 행렬보다 작아야 하므로 체크해줘야함
grid[x1][y1]=='1', 값이 1인 경우에만 파고 들어야겠죠?
grid[x1][y1]='0'; 값을 0으로 만들어서 다시는 안들어 오게 셋팅
queue.offer(new int[] {x1,y1}); 현재 좌표를 큐에 추가해서, 다시 그값에서 사방으로 퍼지면서 조사하기 위해서 셋팅
}
}
답변 1