BOJ(섬의 개수) 4963

작성일 | In

섬의 개수

  • 섬의 개수

  • 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다
  • 섬의 개수를 세는 프로그램 작성
  • 대각선으로의 이동은 어떻게 확인하지 ?
  • 기존에는 dx,dy 배열에 상하좌우를 넣어서 확인해줬다.
  • 그 안에 대각선으로 이동할 경우를 추가해준다.
  • No Image
import sys
sys.setrecursionlimit(10000)
input: sys.stdin.readline


def isSafe(x, y): return 0 <= x < h and 0 <= y < w and arr[x][y] != 0


def DFS(x, y):
    check[x][y] = True
    for i in range(8):
        nx, ny = x+dx[i], y+dy[i]
        if isSafe(nx, ny) and not check[nx][ny]:
            DFS(nx, ny)


dx = [0, 1, 1, 1, 0, -1, -1, -1]
dy = [1, 1, 0, -1, -1, -1, 0, 1]
while True:
    w, h = map(int, input().split())
    if (w, h) == (0, 0):
        break
    arr = [list(map(int, input().split())) for _ in range(h)]
    check = [[False]*w for _ in range(h)]

    cnt = 0
    for i in range(h):
        for j in range(w):
            if arr[i][j] == 1 and not check[i][j]:
                DFS(i, j)
                cnt += 1
    print(cnt)

참고자료 codeplus 참고한블로그

0%