463. Island Perimeter

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

문제 출처

[문제 설명]

육지의 둘레 길이를 구하시오

[처음 생각한 접근 방법]

첫번째 방법 : 총 사각형의 개수와 인접한 사각형의 개수에 따른 규칙이 있을 거라 생각했지만, 떠오르지가 않아서 포기

두번째 방법 : 선택한 지점이 육지면 상하좌우를 다 체크해서 육지가 있을 경우 그 영역은 공동 영역으로 -1해줌.

1.자바코드

class Solution {
    public int islandPerimeter(int[][] grid) {
        int answer = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) answer += 4;
                else {
                    int count = checkOutside(grid, i, j);
                    answer += count;
                }
            }
        }

        return answer;
    }

    private int checkOutside(int[][] grid, int i, int j) {
        int count = 0;
        // 왼
        if (0 <= j-1 && grid[i][j-1] == 1) count--;
        // 우
        if (j+1 < grid[i].length && grid[i][j+1] == 1) count --;
        // 위
        if (0 <= i-1 && grid[i-1][j] == 1) count--;
        // 아래
        if (i+1 < grid.length && grid[i+1][j] == 1) count--;

        return count;
    }
}

2.코틀린코드

class Solution {
    fun islandPerimeter(grid: Array<IntArray>): Int {
        var sum = 0
        fun checkOutline(grid:Array<IntArray>, i:Int, j:Int):Int {
            var neighbor = 0
            // left
            if (0 <= j-1 && grid[i][j-1] == 1) neighbor++
            // right
            if (j+1 < grid[i].size && grid[i][j+1] == 1) neighbor++
            // top
            if (0 <= i-1 && grid[i-1][j] == 1) neighbor++
            // bottom
            if (i+1 <grid.size && grid[i+1][j] == 1) neighbor++

            return neighbor
        }

        for (i in 0..grid.size-1) {
            for (j in 0..grid[i].size-1) {
                if (grid[i][j] == 1) {
                    sum += 4
                    sum -= checkOutline(grid, i,j)
                }
            }
        }

        return sum
    }
}

예상 시간복잡도는 이중배열을 전부 한번씩 방문했으므로 O(n)

공간복잡도는 O(1)입니다.

틀리면 지적 좀.

 

[리트코드 답안]

public class Solution {
    public int islandPerimeter(int[][] grid) {
        int islands = 0, neighbours = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    islands++; // count islands
                    if (i < grid.length - 1 && grid[i + 1][j] == 1) neighbours++; // count down neighbours
                    if (j < grid[i].length - 1 && grid[i][j + 1] == 1) neighbours++; // count right neighbours
                }
            }
        }

        return islands * 4 - neighbours * 2;
    }
}

애초에 상하좌우를 계속 체크할 필요가 없다. 육지의 오른쪽, 아래만 체크하면 중복 될 일 없이 체크 가능함.

육지가 서로 겹치면 둘레가 4일 사각형이 3이 돼고 이웃인 사각형도 둘레가 4가 되야하는데 3이 되므로

총 둘레는 4*사각형의 갯수 - 2*이웃의 개수가 된다.

육지의 왼쪽, 아래쪽을 기준으로 잡아도 상관 없을 듯.