[BOJ 4963] 섬의 개수

Depth First Search

[BOJ 4963] 섬의 개수

문제

구조화

• 단순한 DFS 문제
• 단, 방향이 대각이동이 가능한 case
• 미로탐색, 2차원에서 중요한 point
  • 입력은 w,h 여기서 w는 가로, h는 세로
  • dfs(x,y) 형태 호출 시 x는 가로 길이(w 집합), y는 세로(h 집합) 길이와 관련
  • 2차원 배열의 행열이므로 board indexing은 [y][x]로

예제 시각화

해답

import sys
sys.setrecursionlimit(10**6)
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

def dfs(x,y):
    if x>=w or x<=-1 or y>=h or y<=-1: # 이동 불가능하면 return False
        return False
    
    if board[y][x]==1: # 이동 가능한 지점
        board[y][x]=0 # 방문 표시
        for p in range(8):
            new_x = x+dx[p] # 4방향에 대해
            new_y = y+dy[p]
            dfs(new_x, new_y) # 이동
            
        return True # 이동 후 True

    return False 
    

while True:
    w,h = map(int, input().split())
    if w==0 and h==0:
        break
    else:
        board = []
        dx = [-1, -1, -1, 0, 0, 1, 1, 1]
        dy = [-1, 0, 1, -1, 1, -1, 0, 1]
        for i in range(h):
            data = list(map(int, input().split()))
            board.append(data)
        count = 0
        for c in range(h):
            for p in range(w):
                if dfs(p,c):
                    count+=1
        print(count)