[백준] 4963 섬의 개수 (python 파이썬)

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

---

흔한 구역 개수 구하는 문제. 근데 특이한 건 대각선도 연결되어 있는 걸로 생각해야 하는 게 특이하다. 

그것만 생각하면 나머진 쉬운 문제.

---

아이디어

- 일반적인 상하좌우탐색에서 추가로 대각선 방향도 추가해준다.

---

전체 코드

import sys
sys.setrecursionlimit(10**6)

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

def dfs(x, y):

    if x <= -1 or x >= H or y <= -1 or y >= W:
        return False
    #print(x, y)
    if island[x][y] == 1:
        island[x][y] = 0
        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)
        dfs(x - 1, y)
        dfs(x - 1, y + 1)
        return True
    return False

while 1:
    W, H = map(int, input().split())
    if W == 0 and H == 0:
        break
    answer = 0
    island = []
    for _ in range(H):
        island.append([int(x) for x in sys.stdin.readline().rstrip().split()])
    #print(island)

    for i in range(H):
        for j in range(W):
            if dfs(i, j):
                answer += 1

    print(answer)

---

코드 설명

dx = [0, 0, 1, -1, 1, -1, 1, -1]
dy = [1, -1, 0, 0, 1, -1, -1, 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)
dfs(x - 1, y)
dfs(x - 1, y + 1)

 

기본적인 탐색에서 대각선 방향만 추가해 주면 된다.