PS/Easy
463. Island Perimeter (해석 + 풀이)
우봉수
2023. 1. 10. 02:13
조건:
- row == grid.length
- col == grid[i].length
- 1 <= row, col <= 100
- grid[i][j] is 0 or 1.
- There is exactly one island in grid.
의역: 행과 열로 이루어진 격자판이 있을 때 grid[i][j] = 1이면 해당 지역은 1x1땅이고 grid[i][j] = 0이면 해당 지역은 1x1물 이라고 할때 모든 땅은 대각선이 아닌 수평 수직으로만 이어져 있고 땅 공간 내부에 물이 존재 하지 않는다고 할 때 해당 격자에서 땅의 둘레의 길이를 반환 하라
의역: 해당 그림에서 노랑색이 둘레일때 총 16개의 면이 있으므로 16을 반환
의역: 해당 그림에서 노랑색이 둘레일때 총 4개의 면이 있으므로 4을 반환
의역: 해당 그림에서 노랑색이 둘레일때 총 3개의 면이 있으므로 3을 반환
<풀이>
1. 브루트 포스
class Solution {
private int getSurroundLandCount(int [][]grid, int i,int j){
int land=0;
if(i-1>=0)
if(grid[i-1][j]==1) land++;
if(j-1>=0)
if(grid[i][j-1]==1) land++;
if(j+1<= grid[i].length-1)
if(grid[i][j+1]==1) land++;
if(i+1<=grid.length-1)
if(grid[i+1][j]==1) land++;
return land;
}
// 시간 복잡도 O(n*m) 세로*가로 공간 복잡도 O(1)
public int islandPerimeter(int[][] grid) {
int ans = 0;
// 땅이 있는 모든 경우 체크
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[i].length;j++){
if(grid[i][j]==1) // 해당 땅의 상하좌우에 땅이 있으면 그 수만큼 -
ans+=4-getSurroundLandCount(grid,i,j);
}
}
return ans;
}
}1-1 좀 더 개선한 버전 (검사 방향(↓, →)을 생각 했을 때 사실상 (↑,← ) 방향만 체크하여도 모든 경우를 체크 하는 것이 가능하다 대신 이 경우에는 위와 다르게 각각의 땅의 둘레를 생각해선 안되고 전체적으로 사라지는 둘레를 고려하여야함)
class Solution {
// 위에 타일 각각의 둘레를 구하는 접근 에서 전체적인 땅의 둘레를 구하는 접근으로 봐야 함
// 시간 복잡도 O(n*m) 세로*가로 공간 복잡도 O(1)
public int islandPerimeter(int[][] grid) {
int ans = 0;
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[i].length;j++){
// 어차피 반복을 통해 모든 오른쪽 아래 경우를 검사 함
if(grid[i][j]==1){
ans+=4;
// 위쪽에 땅이랑 이어진 경우 각자의 면에서 하나씩 사라지기 때문에 -2
if(i>0&&grid[i-1][j]==1)
ans-=2;
// 왼쪽에 땅이랑 이어진 경우 각자의 면에서 하나씩 사라지기 때문에 -2
if(j>0&&grid[i][j-1]==1)
ans-=2;
}
}
}
return ans;
}
}2. DFS
class Solution {
private int getPerimeterDFS(int [][]grid,boolean isVisit[][],int i,int j){
// 종료 조건: 범위를 벗어나면 끝
if(i<0||i>= grid.length||j<0||j>=grid[0].length)
return 1;
// 종료 조건2: 해당 위치가 물이라면 끝
if(grid[i][j]==0)
return 1;
// 종료 조건3: 이미 방문한 타일이면 끝
if(isVisit[i][j])
return 0;
// 방문 여부 표시
isVisit[i][j] = true;
// 재귀적인 방법을 통해 타일 검사
int count = getPerimeterDFS(grid,isVisit,i-1,j)
+ getPerimeterDFS(grid,isVisit,i,j-1)
+ getPerimeterDFS(grid,isVisit,i+1,j)
+ getPerimeterDFS(grid,isVisit,i,j+1);
return count;
}
public int islandPerimeter(int[][] grid) {
// 방문 여부를 체크하는 변수
boolean isVisit[][] = new boolean[grid.length][grid[0].length];
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[i].length;j++){
if(grid[i][j]==1)
return getPerimeterDFS(grid,isVisit,i,j);
}
}
return 0;
}
}