알고리즘 공부/LeetCode
[LeetCode] 200. Number of Islands (Java)
EVEerNew
2021. 11. 16. 02:06
반응형
문제
https://leetcode.com/problems/number-of-islands/
Number of Islands - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
풀이
난이도: Medium
DFS나 BFS로 풀 수 있는 문제로, 각 grid의 방문 여부를 저장하는 2차원 boolean 배열 visited로 간단히 구현할 수 있다.
모든 격자 중에 아직 방문하지 않고 1인 격자에서 DFS나 BFS를 실행할 때마다 Island의 count를 1씩 늘려준다.
방문한 격자의 상하좌우의 방향 중에 1인 곳만 방문하면 같이 섬을 이루는 격자는 모두 방문이 가능하므로 섬의 개수를 파악할 수 있다.
코드
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| int[][] changePos = {{1,0},{-1,0}, {0,1}, {0,-1}}; | |
| int row, column; | |
| public void DFS(int r, int c, boolean visited[][], char[][] grid) { | |
| visited[r][c] = true; | |
| int next_r, next_c; | |
| for(int i=0; i<changePos.length ; ++i) { | |
| next_r = r+changePos[i][0]; next_c = c+ changePos[i][1]; | |
| if(next_r<0 || row<= next_r || next_c<0 || column <= next_c) | |
| continue; | |
| if(!visited[next_r][next_c] && grid[next_r][next_c] == '1') | |
| DFS(next_r, next_c, visited, grid); | |
| } | |
| } | |
| public int numIslands(char[][] grid) { | |
| row = grid.length; column = grid[0].length; | |
| boolean[][] visited = new boolean[row][column]; | |
| int count_island = 0; | |
| for(int r=0; r<row ; ++r) | |
| for(int c=0; c<column ;++c) | |
| if(!visited[r][c] && grid[r][c] == '1') { | |
| DFS(r,c, visited, grid); | |
| ++count_island; | |
| } | |
| return count_island; | |
| } | |
| } |
반응형