[알고리즘 연습] 섬(island) 개수 구하기 with DFS

Wan Geun Lee / December 03, 2020

문제

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

Plain Text
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Ex 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


Ex 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

1이 땅이고 0이 물이라고 했을 때 대각선을 제외한 사방이 물로 이뤄진 땅들의 모임을 섬이라고 한다. 이런 섬이 몇 개 있는지를 구하는 문제다.

 

이 문제를 어떻게 풀어야 되나?

1. 섬의 왼쪽 상단을 꼭지점이라 칭하고 꼭지점의 갯수를 구하면 되지 않을까?

(이 부분에 대한 설명은 일단 생략. 추후 작성 예정)

2. 힌트는 DFS. 그런데 DFS가 뭐고 여기에 어떻게 적용하나?

위 방법으로 풀려고 했다가 잘 안되길래 오기가 생겨서 최대한 답을 안보고 힌트를 얻어서 직접 해결해보고 싶었다. 힌트는 DFS, BFS를 응용해서 풀면 된다고 하는데 그걸 여기에 적용하려니 어떻게 해야 되나 막막했다. 이런거 보면 아직 내가 DFS, BFS를 완전히 이해 못하고 있다는 것을 알 수 있었다.

DFS를 복기 하기 위해 일단 DFS가 동작하는 원리를 좀 찾아 봤는데 이진트리, 그래프를 DFS로 순회하는 내용들만 잔뜩 있을 뿐 이 문제에 어떻게 적용해야 되는지 감이 잘 안왔다. 특히 인터넷 설명들은 실제 코드를 기반으로 어떻게 구현하고 동작되는지, 즉 구현에만 초점을 맞춘 설명들이라서 이걸 여기에 어떻게 적용해야 되나 더더욱 막막했다.

DFS의 코드 구현 방법이 아닌 그 핵심 원리를 알고 싶어서 자료를 찾다보니 그나마 나의 궁금증을 충족시켜주는 유튜브 영상을 하나 발견했다.

An image from Notion

출처: https://youtu.be/-wsYtm0x3nw

영상 중간 DFS의 핵심 원리에 대한 설명을 이렇게 말하고 있다.

미로에 갇혔을 때 어떻게 나가야 될까? 한 쪽 벽에 손을 짚고 걸어라. 왼쪽 벽이든 오른쪽 벽이든 한 쪽 벽에 손을 짚고 걸으면 출구로 나갈 수 있다.

미로 찾기에서 알 수 있는 DFS의 원리는 왼쪽 벽에 손을 짚고 그 방향으로 출구가 나올 때까지 왼쪽으로 들어갔다 막혀 있으면 나오고 그 다음 왼쪽 방향(여기선 오른쪽 방향)으로 들어 갔다가 갈림길이 나오면 다시 왼쪽부터 들어가면서 출구를 찾는 것을 반복하며 앞으로 나갔던 것이다.

 

미로 찾기로 보는 DFS의 핵심 원리

  1. 갈림길이 나왔을 때 왼쪽으로 먼저 들어가서 출구가 있는지 탐색한다.
  2. 없으면 나와서 그 다음 왼쪽으로 들어가서 출구가 있는지 탐색한다.
  3. 위 과정을 반복한다.

 

그럼 저 원리를 섬 개수 구하기 문제에 적용하여 풀어보자. 코드 구현은 일단 배제하고 풀이 과정을 차근차근 살펴보기로 했다. 아래와 같은 섬이 있다고 하자.

Plain Text
0
1
2
3
4
5
Input: grid = [
  ["0","1","1","0"],
  ["1","0","0","1"],
  ["0","1","1","0"]
]
Output: 4

grid 배열의 인덱스 표현을 grid[y][x] 라고 한다면 x 방향으로 먼저 순회하면서 섬의 끝자락이 나올 때까지 순회하면 되겠다 라는 생각이 들었다. 섬의 끝자락에 도달하면 섬의 개수를 1 증가하고 그 다음 땅으로 이동하여 또 섬의 끝자락이 나올 때까지 순회하면 될 것 같다는 생각이 들었다. 그 과정을 그림으로 표현하면 다음과 같다.

 

Step 1.

DFS으로 풀꺼니깐 일단 스택을 준비한다. 그리고 인접한 땅을 찾을 대상을 담을 current라는 변수도 준비한다.

An image from Notion

 

Step 2.

배열의 시작인 (0, 0)부터 시작하여 아까 말한 x축 방향부터 순회하면서 땅을 찾는다. 땅을 찾았으면 그 좌표를 스택에 PUSH 한다.

An image from Notion

 

Step 3.

이제 시작이다. 앞으로 한 걸음 나아갔다는 의미로 스택에 있는 좌표를 POP하여 current 변수에 할당한다.

An image from NotionAn image from Notion

 

Step 4.

이제 current에 인접한 땅을 찾는다. 왼쪽, 오른쪽, 위, 아래 중에서 땅이 있는 좌표를 모두 찾아 스택에 넣어주면 된다.

An image from Notion

current에 인접한 땅을 모조리 스택에 PUSH 하는데, 없을 때까지 찾아서 stack.push를 진행한다.

 

Step 5.

더이상 인접한 땅(스택에 넣을 땅)이 없으면 current에 있는 좌표를 visited라는 배열로 옮기고 스택에 가장 마지막으로 넣어두었던 땅 좌표를 POP하여 current로 옮겨준다.

An image from NotionAn image from Notion

이렇게 하는 이유는 그 다음 땅으로 이동하여 인접한 땅을 찾기 위함이라고 보면 된다.

 

그런데 (0, 2)의 땅에는 인접한 땅이 없다. (0, 1)이 땅이긴 하지만 이미 방문한 땅은 스택에 PUSH하지 않는다.

An image from Notion

 

Step 6.

그럼 아까와 마찬가지로 앞으로 나아가기 위해 current에 있는 좌표를 visited 배열로 옮기고 스택에서 다음 땅을 POP 한다.

An image from NotionAn image from Notion

하지만 더 이상 앞으로 나아갈 땅이 없다.

 

Step 7.

더 이상 나아갈 땅이 없으므로 섬의 끝자락이라고 판단하여 섬의 개수를 1 증가한다.

An image from Notion

 

Step 8.

(0, 3)을 보니 물이고 (1, 0)을 보니 땅이다. 그럼 다시 나타난 땅을 스택에 PUSH 한다.

An image from Notion

 

Step 9.

아까처럼 앞으로 나아간다는 의미로 스택에서 땅을 하나 꺼내서(pop) current로 옮겨준다.

An image from NotionAn image from Notion

 

Step 10.

current에 있는 땅에 인접한 땅을 찾아서 스택에 PUSH하려고 보니 인접한 땅이 없다. 그럼 current에 있는 땅을 visited로 옮기고 스택에서 POP을 하거나 없으면 땅을 찾아 나선다.

An image from NotionAn image from Notion

 

Step 11.

더이상 땅이 없기 때문에 visited에 있는 땅들을 섬이라고 판단하여 섬의 개수를 1 증가한다.

An image from Notion

 

Step 12 ~ n.

그 다음 x축 방향으로 땅을 찾고 땅을 찾으면 스택에 PUSH 한 뒤 또 인접한 땅을 찾는다. 이런 식으로 앞의 과정들을 반복하여 배열이 끝날 때까지 순회하여 섬을 찾으면 된다.

An image from Notion

 

위 과정들을 요약하면 다음과 같다.

  1. 지도 배열의 왼쪽 상단부터 시작해서 x축 방향으로 땅이 있을 때까지 x + 1 하면서 땅을 찾아나간다.
  2. 땅에 도달하면 그 땅을 스택에 넣는다(PUSH).
  3. 스택에 PUSH 한 땅을 하나 가져와서(POP) 기준을 잡고 그 땅에 인접한 모든 땅들을 스택에 PUSH 한다.
  4. 더이상 스택에 넣을 땅이 없으면 기준이 되는 땅을 방문했다는 표시를 하고 3번 과정을 되풀이한다.
  5. 더이상 스택에서 POP 할 땅이 없으면 섬을 하나 찾았다는 것으로 보고 섬의 개수를 1 증가한다. 그런 뒤 1번 부터 다시 시작한다. (지도 배열의 요소들을 모두 순회할 때까지)

 

예제를 끝까지 돌려보면 다음과 같다.

An image from Notion

 

코드로 구현해보자.

수도 코드

먼저 수도코드 부터 작성해보자. 의식의 흐름대로 어떻게 작성할지 생각해보면

  1. 일단 제일 먼저 드는 생각은 배열이 2차원 배열로 주어지니깐 그걸 모두 순회하려면 for loop도 2중으로 있어야겠지?
  2. 땅을 찾으면 스택에 넣고
  3. 스택에 넣은 땅을 기준으로 잡고
  4. 기준이 되는 땅 주위의 땅들을 모두 스택에 넣자.

일단 여기까지 작성해보자. (배열 참조 시 out of index는 잠깐 무시하고 그냥 진행해보자)

Plain Text
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def numOfIsland(grid: Array[Array[Char]]): Int = {
  for i <- 0 to grid.length
    for j <- 0 to grid[i].length // 1
      if (grid[i][j]는 땅인가?) { // 2
        val stack = 스택 생성 // 2
        dfs(grid, (i, j)) // 2, 3
      }
}

def dfs(grid: Array[Array[Char]], position: (Int, Int), stack: Stack) {
  // 4
  if (grid[position.y][position.x - 1]는 땅인가?) {
    stack.push(position)
  }
  if (grid[position.y][position.x + 1]는 땅인가?) {
    stack.push(position)
  }
  if (grid[position.y - 1][position.x]는 땅인가?) {
    stack.push(position)
  }
  if (grid[position.y + 1][position.x]는 땅인가?) {
    stack.push(position)
  }
}

그 다음은 어떻게 할까?

  1. 스택에 넣을 땅이 더이상 없으면? 기준이 되는 땅은 Visited 표시를 한다.
  2. 그런 뒤 스택에서 POP을 해서 그 땅을 기준으로 또 인접한 땅을 모두 스택에 PUSH 한다.
Plain Text
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def numOfIsland(grid: Array[Array[Char]]): Int = {
  for i <- 0 to grid.length
    for j <- 0 to grid[i].length
      if (grid[i][j]는 땅인가?) {
        val stack = 스택 생성
        val visited = Array[(Int, Int)] 할당하기
        dfs(grid, (i, j), stack, visited)      
      }
}

def dfs(grid: Array[Array[Char]], position: (Int, Int), stack: Stack, visited: Array[(Int, Int)]) {
  if (grid[position.y][position.x - 1]는 땅인가?) {
    stack.push(position)
  }
  if (grid[position.y][position.x + 1]는 땅인가?) {
    stack.push(position)
  }
  if (grid[position.y - 1][position.x]는 땅인가?) {
    stack.push(position)
  }
  if (grid[position.y + 1][position.x]는 땅인가?) {
    stack.push(position)
  }

  visited += position // 1
  dfs(grid, stack.pop, visited) // 2
}

그 다음은?

  1. 스택에서 POP을 했는데 만약 아무 것도 없다면, visited에 있는 땅들을 섬으로 확정하고 끝낸다.
Plain Text
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def numOfIsland(grid: Array[Array[Char]]): Int = {
  val numIslands = 0

  for i <- 0 to grid.length
    for j <- 0 to grid[i].length
      if (grid[i][j]는 땅인가?) {
        val stack = 스택 생성
        val visited = Array[(Int, Int)] 할당하기
        dfs(grid, (i, j), visited, numIslands)
      }
}

def dfs(grid: Array[Array[Char]], 
        position: (Int, Int), 
        stack: Stack, 
        visited: Array[(Int, Int)],
        numIslands: Int) {
  if (grid[position.y][position.x - 1]는 땅인가?) {
    stack.push(position)
  }
  if (grid[position.y][position.x + 1]는 땅인가?) {
    stack.push(position)
  }
  if (grid[position.y - 1][position.x]는 땅인가?) {
    stack.push(position)
  }
  if (grid[position.y + 1][position.x]는 땅인가?) {
    stack.push(position)
  }

  visited += position

  val newStandard = stack.pop
  if (newStandard가 있는가?) { // 1
    dfs(grid, , visited)
  }
  return numIslands + 1 // 이렇게 하는게 맞나? 일단 이 부분은 구현하면서 고쳐보자
}

잠깐! 근데 스택에 PUSH 할 때 이미 방문한 땅이면 PUSH 하지 말아야 하는데 그 부분이 빠졌다. 그 부분을 보완해보자.

Plain Text
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def numOfIsland(grid: Array[Array[Char]]): Int = {
  val numIslands = 0

  for i <- 0 to grid.length
    for j <- 0 to grid[i].length
      if (grid[i][j]는 땅인가?) {
        val stack = 스택 생성
        val visited = Array[(Int, Int)] 할당하기
        dfs(grid, (i, j), visited, numIslands)
      }
}

def dfs(grid: Array[Array[Char]], 
        position: (Int, Int), 
        stack: Stack, 
        visited: Array[(Int, Int)],
        numIslands: Int) {
  if (grid[position.y][position.x - 1]는 땅인가?) {
    push(stack, (position.x - 1, position.y), visited)
  }
  if (grid[position.y][position.x + 1]는 땅인가?) {
    push(stack, (position.x + 1, position.y), visited)
  }
  if (grid[position.y - 1][position.x]는 땅인가?) {
    push(stack, (position.x, position.y - 1), visited)
  }
  if (grid[position.y + 1][position.x]는 땅인가?) {
    push(stack, (position.x, position.y + 1), visited)
  }

  visited += position

  val newStandard = stack.pop
  if (newStandard가 있는가?) { // 1
    dfs(grid, , visited)
  }
  return numIslands + 1 // 이렇게 하는게 맞나? 일단 이 부분은 구현하면서 고쳐보자
}

def stackPush(stack: Stack, position: (Int, Int), visited: Array[(Int, Int)]) {
  if (position이 visited 배열이 없을 경우에만) {
    stack.push(position)
  }
}

수도 코드 작성은 일단 여기까지 하도록 하고 실제 코드로 구현해보자.

 

실제 코드

Scala
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import scala.collection.mutable
import scala.util.Try

object Solution {
  def numIslands(grid: Array[Array[Char]]): Int = {
    var numIslands = 0
    var visited = mutable.Map[(Int, Int), Boolean]()

    for (i <- 0 until grid.length) {
      for (j <- 0 until grid(i).length) {
        if (!isVisited((i, j), visited) && grid(i)(j) == '1') {
          val stack = new mutable.Stack[(Int, Int)]()

          push(stack, (i, j), visited)
          dfs(grid, stack, visited)
          numIslands += 1
        }
      }
    }

    numIslands
  }

  private def dfs(grid: Array[Array[Char]],
                  stack: mutable.Stack[(Int, Int)],
                  visited: mutable.Map[(Int, Int), Boolean]): Unit = {
    val newStandard = Try(stack.pop()).toOption

    newStandard match {
      case Some(position) =>
        visited.put(position, true)

        if (position._2 > 0 && !isVisited((position._1, position._2 - 1), visited) && grid(position._1)(position._2 - 1) == '1') {
          push(stack, (position._1, position._2 - 1), visited)
          dfs(grid, stack, visited)
        }
        if (position._2 < grid(position._1).length - 1 && !isVisited((position._1, position._2 + 1), visited) && grid(position._1)(position._2 + 1) == '1') {
          push(stack, (position._1, position._2 + 1), visited)
          dfs(grid, stack, visited)
        }
        if (position._1 > 0 && !isVisited((position._1 - 1, position._2), visited) && grid(position._1 - 1)(position._2) == '1') {
          push(stack, (position._1 - 1, position._2), visited)
          dfs(grid, stack, visited)
        }
        if (position._1 < grid.length - 1 && !isVisited((position._1 + 1, position._2), visited) && grid(position._1 + 1)(position._2) == '1') {
          push(stack, (position._1 + 1, position._2), visited)
          dfs(grid, stack, visited)
        }
      case None =>
    }
  }

  private def push(stack: mutable.Stack[(Int, Int)], position: (Int, Int), visited: mutable.Map[(Int, Int), Boolean]): Unit =
    if (!isVisited(position, visited)) {
      stack.push(position)
    }

  private def isVisited(position: (Int, Int), visited: mutable.Map[(Int, Int), Boolean]) = {
    visited.get((position._1, position._2)).isDefined
  }
}

수도 코드에서 생각했던 부분을 실제로 구현해보니 섬 개수를 증가시키는 부분이 생각과는 달랐다. 어떻게 달랐을까?

  • 수도 코드엔 dfs 함수가 끝나면 섬 개수를 증가 시켰는데 그게 섬 발견의 조건은 아니었다. (수도코드에서 잘못 생각함)
  • 수도 코드엔 방문했던 땅에 대해 패스하는 로직이 없었는데 실제 코드로 구현하면서 추가됐다.

 

다른 사람들은 어떻게 풀었을까? 혹은 다른 방법은 뭐가 있을까?

1. DFS로 풀긴 했는데 Stack과 visited를 안 씀

다른 사람들 푼걸 보니 인접한 땅을 넣을 스택과 땅에 방문했다 라는 표시를 하기 위한 visited 저장소를 따로 안쓰고 해결한 것을 볼 수 있었다. 어떻게 스택과 visited를 안쓰고 해결할 수 있었던 것일까?

사실 스택을 아예 안썼다라기 보단 함수 콜스택을 활용한 것이고, 방문 했다라는 표시는 따로 visited에 할 필요 없이 원본 grid에 땅을 다른 문자로 표시하면 되는 거였다. 나는 DFS는 스택을 써야 된다라는 생각에 사로잡혀 Stack을 따로 할당해서 그걸 활용했는데 사실 그럴 필요가 없었다. 그렇게 푼 결과물은 다음과 같다.

Scala
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
object Solution {
  def numIslands(grid: Array[Array[Char]]): Int = {
    var numIslands = 0

    for (i <- 0 until grid.length) {
      for (j <- 0 until grid(i).length) {
        if (grid(i)(j) == '1') {
          dfs(grid, (i, j))
          numIslands += 1
        }
      }
    }

    numIslands
  }

  private def dfs(grid: Array[Array[Char]], current: (Int, Int)): Unit = {
    // current는 x로 치환하고
    grid(current._1)(current._2) = 'x'
    // left 탐색
    if (current._2 - 1 >= 0 && grid(current._1)(current._2 - 1) == '1') {
      dfs(grid, (current._1, current._2 - 1))
    }
    // right 탐색
    if (current._2 + 1 < grid(current._1).length && grid(current._1)(current._2 + 1) == '1') {
      dfs(grid, (current._1, current._2 + 1))
    }
    // up 탐색
    if (current._1 - 1 >= 0 && grid(current._1 - 1)(current._2) == '1') {
      dfs(grid, (current._1 - 1, current._2))
    }
    // down 탐색
    if (current._1 + 1 < grid.length && grid(current._1 + 1)(current._2) == '1') {
      dfs(grid, (current._1 + 1, current._2))
    }
  }
}

grid에 바로 방문했다라는 표시를 하니 dfs 재귀 호출 시 땅인지 검사할 때 이미 방문한 땅은 1이 아닌 다른 문자라서 dfs 탐색을 안하게 된 것이다.

2. BFS로 풀기

위에서 DFS로 했으니깐 BFS의 원리를 알기만 하면 금방 풀 수 있을거 같았다. BFS의 원리를 보면 다음과 같다.

  1. 루트에서 시작한다.
  2. 루트에 인접한 노드들을 큐에 저장한다.
  3. 저장할 노드가 없으면 dequeue를 해서 하나 가져온다.
  4. 3번 과정에서 가져온 노드를 기준으로 인접한 노드를 모두 큐에 enqueue 한다.
  5. 3 ~ 4 과정을 반복한다.
  6. 모든 노드를 방문하면 탐색을 마친다.

 

이 문제에 위 원리를 적용하면 어떻게 될까?

  1. 루트 (0, 0)에서 시작한다. (루트를 current에 저장)
  2. current에 인접한 땅을 큐에 저장한다.
  3. 저장할 땅이 없으면 dequeue해서 땅을 가져오고 current에 저장한다. (기존에 current에 있던 땅은 visited로 옮긴다)
  4. 2~3번 과정을 반복한다.
  5. 더 이상 큐에 넣을 땅이 없으면 visited에 있는 땅들을 섬으로 확정한다.
  6. 모든 땅을 방문하면 탐색을 마친다.
Scala
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import scala.collection.mutable
import scala.util.Try

object Solution {
  def numIslands(grid: Array[Array[Char]]): Int = {
    var numIslands = 0

    for (i <- 0 until grid.length) {
      for (j <- 0 until grid(i).length) {
        if (grid(i)(j) == '1') {
          bfs(grid, (i, j))
          numIslands += 1
        }
      }
    }

    numIslands
  }

  private def bfs(grid: Array[Array[Char]], current: (Int, Int)): Unit = {
    var done = false
    val queue = new mutable.Queue[(Int, Int)]()
    var newCurrent = current

    while (!done) {
      // current는 x로 치환하고
      grid(newCurrent._1)(newCurrent._2) = 'x'

      // left 탐색
      if (newCurrent._2 - 1 >= 0 && grid(newCurrent._1)(newCurrent._2 - 1) == '1') {
        grid(newCurrent._1)(newCurrent._2 - 1) = 'x'
        queue.enqueue((newCurrent._1, newCurrent._2 - 1))
      }
      // right 탐색
      if (newCurrent._2 + 1 < grid(newCurrent._1).length && grid(newCurrent._1)(newCurrent._2 + 1) == '1') {
        grid(newCurrent._1)(newCurrent._2 + 1) = 'x'
        queue.enqueue((newCurrent._1, newCurrent._2 + 1))
      }
      // up 탐색
      if (newCurrent._1 - 1 >= 0 && grid(newCurrent._1 - 1)(newCurrent._2) == '1') {
        grid(newCurrent._1 - 1)(newCurrent._2) = 'x'
        queue.enqueue((newCurrent._1 - 1, newCurrent._2))
      }
      // down 탐색
      if (newCurrent._1 + 1 < grid.length && grid(newCurrent._1 + 1)(newCurrent._2) == '1') {
        grid(newCurrent._1 + 1)(newCurrent._2) = 'x'
        queue.enqueue((newCurrent._1 + 1, newCurrent._2))
      }

      Try(queue.dequeue()).toOption match {
        case Some(next) =>
          newCurrent = next
        case None =>
          done = true
      }
    }
  }
}

3. Union Find

union find라는 방법도 있다는데 그거는 추후 알아보기로 하자. 처음 보는 방법인데...

그 외