Golang Algorithm - countIslands

문제설명 : 

세로와 가로의 길이가 각각 R, M인 2차원 R X M 배열 grid가 주어졌을 때, '1'은 땅을 의미하고 '0' 은 물을 의미합니다. 주어진 2차원 배열에 존재하는 섬의 개수를 리턴해야 합니다.

즉,  0은 물이고 1이 땅이니까 1끼리 모여있는 섬의 개수를 리턴하면 됩니다. 그리고 한번 체크한 1에 대해서는 중복해서 체크하지 않는 것도 핵심입니다. 

입력

인자 1 : grid

• 세로와 가로의 길이가 각각 R, M인 2차원 배열
• arr.length는 R
• arr[i].length는 M
• arr[i][j]는 0 또는 1
  
  

출력

• number 타입을 리턴해야 합니다.

주의사항

• 섬이란 물로 둘러싸여 있는 땅을 말합니다.
• 가로 혹은 세로로 땅이 연결되어 있는 경우 하나의 섬으로 간주합니다.
• 2차원 배열의 범위 밖은 물로 둘러싸여 있다고 가정합니다.

 

go 풀이코드 1:

package main

import "fmt"

func countIslands(grid [][]string) int {
	//dfs solution
	HEIGHT := len(grid)
	WIDTH := 0

	if HEIGHT > 0 {
		WIDTH = len(grid[0])
	}
	count := 0

	for row := 0; row < HEIGHT; row++ {
		for col := 0; col < WIDTH; col++ {
			if grid[row][col] == "0" {
				continue
			}
			count++
			searchIsland(row, col, grid, HEIGHT, WIDTH)
		}

	}
	return count
}

func searchIsland(row int, col int, grid [][]string, HEIGHT int, WIDTH int) {
	if row < 0 || col < 0 || row >= HEIGHT || col >= WIDTH {
		return
	}

	if grid[row][col] == "0" {
		return
	}

	grid[row][col] = "0"
	searchIsland(row-1, col, grid, HEIGHT, WIDTH)
	searchIsland(row+1, col, grid, HEIGHT, WIDTH)
	searchIsland(row, col-1, grid, HEIGHT, WIDTH)
	searchIsland(row, col+1, grid, HEIGHT, WIDTH)
}

func main() {
	grid := [][]string{
		{"0", "1", "1", "1"},
		{"0", "1", "1", "1"},
		{"1", "1", "0", "0"},
	}
	result := countIslands(grid)
	fmt.Println(result) // --> 1

	grid = [][]string{
		{"0", "1", "1", "1", "0"},
		{"0", "1", "0", "0", "0"},
		{"0", "0", "0", "1", "0"},
		{"1", "1", "0", "1", "0"},
		{"1", "1", "0", "1", "0"},
	}
	result = countIslands(grid)
	fmt.Println(result) // --> 3
}

 

 

go 풀이코드 2:

package main

import (
	"fmt"
)

func countIslands(grid [][]string) int {
	// 방문 여부를 체크하기 위한 2차원 배열 생성
	visited := make([][]bool, len(grid))
	for i := 0; i < len(grid); i++ {
		visited[i] = make([]bool, len(grid[0]))
	}
	count := 0

	// 상하좌우 이동을 위한 배열
	dx := []int{-1, 1, 0, 0}
	dy := []int{0, 0, -1, 1}

	// DFS를 위한 함수 정의
	var dfs func(int, int)
	dfs = func(x, y int) {
		visited[x][y] = true

		// 상하좌우 인접 노드 방문
		for i := 0; i < 4; i++ {
			nx := x + dx[i]
			ny := y + dy[i]

			// 범위를 벗어나거나, 물이라면 방문하지 않음
			if nx < 0 || ny < 0 || nx >= len(grid) || ny >= len(grid[0]) || grid[nx][ny] == "0" {
				continue
			}

			// 방문하지 않은 인접 노드 방문
			if !visited[nx][ny] {
				dfs(nx, ny)
			}
		}
	}

	// 모든 노드에 대해서 DFS 실행
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if !visited[i][j] && grid[i][j] == "1" {
				count++
				dfs(i, j)
			}
		}
	}

	return count
}

func main() {
	grid := [][]string{
		{"0", "1", "1", "1"},
		{"0", "1", "1", "1"},
		{"1", "1", "0", "0"},
	}
	result := countIslands(grid)
	fmt.Println(result) // --> 1

	grid = [][]string{
		{"0", "1", "1", "1", "0"},
		{"0", "1", "0", "0", "0"},
		{"0", "0", "0", "1", "0"},
		{"1", "1", "0", "1", "0"},
		{"1", "1", "0", "1", "0"},
	}
	result = countIslands(grid)
	fmt.Println(result) // --> 3
}