[Leetcode/DFS, BFS, Matrix] 463. Island Perimeter

Greedy + Adjacency Counting Approach

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        # Initialize perimeter
        perimeter = 0
        
        # Iterate over each cell in the grid
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # If the cell is land
                if grid[i][j] == 1:
                    # Add 4 for the current cell
                    perimeter += 4
                    
                    # Check if there is land above and subtract 2 if true
                    if i > 0 and grid[i - 1][j] == 1: # If the current land cell has another land cell directly above it
                        perimeter -= 2 #  then subtract 2 from the perimeter.
                        
                    # Check if there is land to the left and subtract 2 if true
                    if j > 0 and grid[i][j - 1] == 1: # If the current land cell has another land cell directly to the left of it
                        perimeter -= 2 
                        
        return perimeter

✅ 왜 위쪽(i-1)과 왼쪽(j-1)만 확인하나요?

그 이유는 코드가 행 우선(row-wise), 왼쪽에서 오른쪽(left to right) 방향으로 순차적으로 그리드를 탐색하기 때문입니다.

즉, 현재 셀 (i, j)를 확인할 때:

• 위쪽(i-1)과 왼쪽(j-1) 셀은 이미 확인했던 셀입니다.
• 하지만 아래쪽(i+1)과 오른쪽(j+1)은 아직 확인하지 않았기 때문에, 나중에 탐색됩니다.

그래서 공유된 변(edge)은 이미 확인한 위나 왼쪽만 고려하면 충분합니다.

 

🧱 예시:

[1, 1]

• 왼쪽 셀: 4를 더함
• 오른쪽 셀: 4를 더함
• 오른쪽 셀은 왼쪽 셀이 land(1)인지 확인 → 공유된 변이므로 2를 빼줌
  👉 총 둘레: 4 + 4 - 2 = 6 ✅

❌ 만약 아래쪽/오른쪽도 확인한다면?

공유된 변을 두 번 빼게 되어 오류가 생깁니다.

• 왼쪽 셀에서 오른쪽 셀을 보고 -2
• 오른쪽 셀에서도 왼쪽 셀을 다시 보고 또 -2
  👉 총 4를 빼버려서 둘레가 작아짐 ❌

💡 정리:

• 위쪽과 왼쪽만 확인하면, 각 공유된 변을 한 번만 처리할 수 있습니다.
• 불필요한 중복 체크를 피할 수 있어서 효율적이고, 코드도 간단합니다.
• 아래쪽과 오른쪽을 보려면 방문 여부(visited) 저장 같은 추가 처리가 필요해져서 복잡해집니다.