row x col
로 된 grid
가 주어진다. grid[i][j]
가 1
이라면 땅, 0
은 물을 나타낸다.
한 칸은 가로/세로로 연결되고 대각선으로 이동할 수 없다.
grid
에는 완전히 물로 둘러싸여 있고 하나의 섬(연결된 하나 이상의 육지 -> grid[i][j] == 1)이 있다.
grid
는 호수가 없다. (육지 내에 뜬금없이 물이 있다던가 하는) 하나의 칸은 한 변의 길이가 1인 정사각형이다. grid
는 직사각형이고 너비와 높이는 100을 초과하지 않는다. 섬의 둘레를 출력하라.
Example 1
Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Example 2
Input: grid = [[1]]
Output: 4
Example 3
Input: grid = [[1,0]]
Output: 4
BFS와 DFS에 많이 약하다고 느껴져서 이번만큼은 풀이를 보지 않고 풀어보기로 결심했다.
문제를 처음 보고 육지(1)와 인접한 변이 아닌 나머지 변의 수를 어떻게 구할지부터 머리가 아파왔다.. 어떤 grid가 들어오든 정확히 계산될 수 있게 하려면 육지를 기준으로 할 지, 물을 기준으로 할 지, 기준을 잡는다면 어떻게 계산할지 노트로 주구장창 그려보며 고민했다.
- x, y좌표가 상하좌우로 이동할 수 있는 거리를 계산할
int[][] move
를 전역으로 선언한다.grid
의 한 칸씩 반복하며 값이 1인(육지) 칸의x값
와j값
을 찾고bfs()
메서드로 보낸다. 값이 0인(물) 칸은 계산하지 않는다.bfs
메서드는grid
와x값(i)
,y값(j)
을 전달받는다.x값(i)
,y값(j)
으로Position
객체를 생성한다.move
길이만큼 반복하며 현재 위치에서 상, 하, 좌, 우로 이동했을 시 의nowX
,nowY
를 두고grid[nowX][nowY]
가 유효한 위치인지(따로 boolean체크로 뺐다.), 그 위치가 몇 개의 육지와 인접해있는지 확인한다.- 인접한 육지의 개수를 카운트(
cnt
)한다.- 계산할 변의 개수를 구하기 위해
4 - cnt
해주었다. (4개의 변에서 육지와 붙어 있는 변의 개수를 빼준다.)- return된 수를 더하고 출력한다.
class Solution {
static int[][] move = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 상하좌우
public int islandPerimeter(int[][] grid) {
int sideLength = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == 1) {
sideLength += bfs(grid, i, j);
}
}
}
return sideLength;
}
private static int bfs(int[][] grid, int xValue, int yValue) {
int cnt = 0;
Position position = new Position(xValue, yValue);
int x = position.x;
int y = position.y;
for (int i = 0; i < move.length; i++) {
int nowX = x + move[i][0];
int nowY = y + move[i][1];
if (chk(nowX, nowY, grid.length, grid[0].length) && (grid[nowX][nowY] == 1)) cnt++;
}
return 4 - cnt;
}
private static boolean chk(int x, int y, int x_length, int y_length) {
if (x < 0 || y < 0 || x >= x_length || y >= y_length) return false;
else return true;
}
}
class Position {
int x;
int y;
Position(int x, int y) {
this.x = x;
this.y = y;
}
}
맨날 머리 싸매던 BFS를 혼자 풀어보고 통과했다는 것에 감격한 새벽이었다.. ✨