[leetcode] Island Perimeter

문제

• 문제 링크
• 지도를 나타내는 2차원 배열 grid가 주어진다. grid[i][j] 값이 1이면 땅을 의미하고, 0이면 물을 의미한다. grid 안에 있는 섬의 둘레를 구해야 한다.
  • grid는 물로 둘러쌓여 있고, 안에는 단 하나의 섬이 존재한다.
  • 섬 안에는 호수가 없다. 호수는 섬 외부에 있는 물과 연결되지 않은 물이다.
  • 하나의 셀은 한 변의 길이가 1인 정사각형이다.
• 제약 조건
  • grid 가로 세로 길이: 1 <= row, col <= 100
• 예시
  

풀이

풀기 전

• 복잡한 문제인가 싶었는데, 주어진 조건 하에서는 간단한 문제였다. grid를 순회하다가 땅을 만났을 때, 상하좌우에 있는 셀이 물이거나 범위를 벗어나면 섬의 둘레에 포함된다. 모든 땅에 대해 조건을 만족하는 곳을 찾으면 된다.

코드

class Solution {
    public int islandPerimeter(int[][] grid) {
        int ans = 0;

        int row = grid.length;
        int col = grid[0].length;

        int[] dy = {-1, 1, 0, 0};
        int[] dx = {0, 0, 1, -1};

        int ny, nx;
		// grid 순휘한다.
        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if (grid[i][j] == 0)  // 탐색하는 곳이 물이면 건너뛴다.
                    continue;

				// 상하좌우에 있는 셀을 살핀다.
                for (int k=0; k<4; k++) {
                    ny = i + dy[k];
                    nx = j + dx[k];

					// 상하좌우에 있는 셀이 범위를 벗어나거나 물이면 둘레에 1을 더한다.
                    if (ny < 0 || ny >= row || nx < 0 || nx >= col || grid[ny][nx] == 0)
                        ans++;
                }
            }
        }
        return ans;
    }
}

푼 후

• 섬 안에 호수가 없기도 하고, 섬이 하나밖에 없어서 단순하게 풀 수 있었다.
• 모든 셀을 한 번씩 순회하기 때문에 시간 복잡도는 O(row*col)이다. 선형적으로 쓰이는 메모리는 없으므로 공간 복잡도는 O(1)이다.