문제를 본 날: 2022년 11월 9일

문제를 푼 날: 2022년 11월 9일 오후 8:43 (GMT+9)

https://leetcode.com/problems/number-of-islands/

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

Solution

풀고 나서 보니 이 문제를 푼 해답들을 보면 대부분 DFS가 빨랐다.

유용한 문법. pair나 tuple 자료형을 한 번에 각각의 변수에 초기화 하는 방법.

tie()를 이용하면 편리하긴 했지만, 이것을 초기화에 사용할 수는 없었는데, c++17부터 지원하는 아래 방법을 통해서는 가능하다. 더 좋아진 것 같다. 그렇지만 타입에 대한 부분을 조심해야 할 필요가 있는 것 같다. 두 번째와 세 번째 링크를 제대로 읽어보면 좋을 것 같다.

https://stackoverflow.com/questions/39103792/initializing-multiple-references-with-stdtie