99클럽 코테 스터디 6일차 TIL + DFS

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

# 4963 섬의 개수

import sys
sys.setrecursionlimit(10**7)

input = sys.stdin.readline

dx = [1,-1,0,0,1,1,-1,-1]
dy = [0,0,1,-1,1,-1,1,-1]

def dfs(x,y):
    if x < 0 or x >= h or y < 0 or y >= w:
        return
    
    if graph[x][y] == 1:
        graph[x][y] = 0  # 방문처리

        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx,ny)

while True:
    answer = 0
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break
    
    graph = [list(map(int, input().split())) for _ in range(h)]
    
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                dfs(i,j)
                answer += 1
    print(answer)

 

• 모든 지점을 돌아다니며 Land 가 상하좌우대각선 으로 붙어있는 섬을 찾아야 하므로 dfs 알고리즘을 이용했다.
• 입력 받은 후 땅을 만나면 섬으로 인지하기 때문에 dfs 함수를 태워 붙어있는 땅을 구할 수 있도록 한다.
• 이때 가로 , 세로 를 입력받은 h,w 로 헷갈리지 않도록 주의해야 할거 같다..!
• 또한, 방문처리를 따로 리스트를 두지 않고 0으로 판단했다.