[JAVA | LeetCode] 463. Island Perimeter

출처 - https://leetcode.com/problems/island-perimeter/

문제

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

제한사항

• 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 안에 정확한 하나의 섬이 있다.

풀이

BFS와 DFS에 많이 약하다고 느껴져서 이번만큼은 풀이를 보지 않고 풀어보기로 결심했다.

문제를 처음 보고 육지(1)와 인접한 변이 아닌 나머지 변의 수를 어떻게 구할지부터 머리가 아파왔다.. 어떤 grid가 들어오든 정확히 계산될 수 있게 하려면 육지를 기준으로 할 지, 물을 기준으로 할 지, 기준을 잡는다면 어떻게 계산할지 노트로 주구장창 그려보며 고민했다.

1. x, y좌표가 상하좌우로 이동할 수 있는 거리를 계산할 int[][] move를 전역으로 선언한다.
2. grid의 한 칸씩 반복하며 값이 1인(육지) 칸의 x값와 j값을 찾고 bfs()메서드로 보낸다. 값이 0인(물) 칸은 계산하지 않는다.
3. bfs메서드는 grid와 x값(i), y값(j)을 전달받는다.
4. x값(i), y값(j)으로 Position 객체를 생성한다.
5. move 길이만큼 반복하며 현재 위치에서 상, 하, 좌, 우로 이동했을 시 의 nowX, nowY를 두고 grid[nowX][nowY]가 유효한 위치인지(따로 boolean체크로 뺐다.), 그 위치가 몇 개의 육지와 인접해있는지 확인한다.
6. 인접한 육지의 개수를 카운트(cnt)한다.
7. 계산할 변의 개수를 구하기 위해 4 - cnt해주었다. (4개의 변에서 육지와 붙어 있는 변의 개수를 빼준다.)
8. 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를 혼자 풀어보고 통과했다는 것에 감격한 새벽이었다.. ✨