BOJ / 4963번 / 섬의 개수 [Go][Python3]

👩🏻‍💻 문제

4963번: 섬의 개수

---

✍🏻 풀이

🎨 Go

// https://www.acmicpc.net/problem/4963
package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	graph   [][]int
	visited [][]bool
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	for {
		var w, h int
		fmt.Fscanln(reader, &w, &h)

		if w == 0 && h == 0 {
			break
		}

		graph = make([][]int, h)
		for i := 0; i < h; i++ {
			graph[i] = make([]int, w)
		}
		visited = make([][]bool, h)
		for i := 0; i < h; i++ {
			visited[i] = make([]bool, w)
		}
		for i := 0; i < h; i++ {
			for j := 0; j < w; j++ {
				fmt.Fscanf(reader, "%d ", &graph[i][j])
			}
		}

		var numOfIslands int
		for i := 0; i < h; i++ {
			for j := 0; j < w; j++ {
				if !visited[i][j] && graph[i][j] == 1 { // 섬이면서 방문하지 않은 경우
					numOfIslands++
					dfs(i, j)
				}
			}
		}
		fmt.Fprintln(writer, numOfIslands)
	}
}

func dfs(h, w int) {
	visited[h][w] = true
	var startH, startW, endH, endW = h, w, h, w
	if h-1 >= 0 {
		startH--
	}
	if h+1 < len(graph) {
		endH++
	}
	if w-1 >= 0 {
		startW--
	}
	if w+1 < len(graph[h]) {
		endW++
	}

	// 상, 하, 좌, 우, 대각선 탐색
	for i := startH; i <= endH; i++ {
		for j := startW; j <= endW; j++ {
			if graph[i][j] == 1 && !visited[i][j] { // 섬이면서 방문하지 않은 경우 재귀
				dfs(i, j)
			}
		}
	}
}

🎨 Python3

# https://www.acmicpc.net/problem/4963
import sys

sys.setrecursionlimit(2500) # python 재귀함수 호출 횟수는 1000회이므로 설정 변경

graph = []
visited = []

def dfs(h, w):
    global visited
    global graph
    visited[h][w] = True
    start_h, start_w, end_h, end_w = h, w, h, w
    if h-1 >= 0:
        start_h -= 1
    if h+1 < len(graph):
        end_h += 1
    if w+1 < len(graph[h]):
        end_w += 1
    if w-1 >= 0:
        start_w -= 1

    for i in range(start_h, end_h+1):
        for j in range(start_w, end_w+1):
            if graph[i][j] == 1 and not visited[i][j]:
                dfs(i, j)

if __name__ == "__main__":
    while True:
        w, h = list(map(int, sys.stdin.readline().split()))
        if w == 0 and h == 0:
            break

        graph = []
        visited = [[False for i in range(w)] for j in range(h)]
        for i in range(h):
            graph.append(list(map(int, sys.stdin.readline().split())))

        num_of_islands = 0
        for i in range(h):
            for j in range(w):
                if not visited[i][j] and graph[i][j] == 1:
                    num_of_islands += 1
                    dfs(i, j)
        print(num_of_islands)