백준 4963번 섬의 개수 파이썬 DFS

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

4963번: 섬의 개수

 

 

 

답안

import sys
sys.setrecursionlimit(10**4) # 재귀스택 확장

def dfs(x, y):
    if x < 0 or y < 0 or y >= w or x >= h:
        return False
    
    if graph[x][y] == 1:
        graph[x][y] = 0
        dfs(x-1, y) # 반 시계 방향 순환
        dfs(x-1, y-1)
        dfs(x, y-1)
        dfs(x+1, y-1)
        dfs(x+1, y)
        dfs(x+1, y+1)
        dfs(x, y+1)
        dfs(x-1, y+1)
        return True
    return False

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

---

이 문제에서 대각선에 섬이 있어도 인접하다고 써져 있으므로

DFS를 8방향으로 설정해야 한다.

한번 노드를 탐색하면 8방향 전부 다 탐색해야 한다.

그림으로 설명하자면 아래와 같이 설명할 수 있다.

 

탐색방향그림

 

DFS 함수에서 파란색 부분을 전부 탐색해 줘야 하므로 8개의 함수를 호출해 줘야 한다.

def dfs(x, y):
    if x < 0 or y < 0 or y >= w or x >= h:
        return False
    
    if graph[x][y] == 1: # 8번의 함수 호출
        graph[x][y] = 0
        dfs(x-1, y) # 반 시계 방향 순환
        dfs(x-1, y-1)
        dfs(x, y-1)
        dfs(x+1, y-1)
        dfs(x+1, y)
        dfs(x+1, y+1)
        dfs(x, y+1)
        dfs(x-1,y+1)
        return True
    return False