[Python] 백준 알고리즘 4963번 - 섬의 개수

[Python] 백준 알고리즘 4963번 - 섬의 개수

 

문제 출처 : https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

문제 - 4963 - 섬의 개수

접근방식

 기존의 DFS / BFS 문제와 유사한 문제이다. 차이점은 이제 대각선의 방향이 추가되어 기존의 4방향 그래프 탐색 문제에서 8방향 탐색 문제로 바뀐 점이다.

# 방향
dx = [1, -1, 0, 0, 1, 1, -1, -1]
dy = [0, 0, 1, -1, 1, -1, 1, -1]

# 탐색
 for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]

따라서 위의 코드처럼 방향을 추가하여 탐색의 방향을 4방향이 아닌 8방향으로 해서 기존의 DFS / BFS 문제 방식으로 진행을 하면 된다. 

 

구현 코드

import sys
from collections import deque

# 탐색의 방향
dx = [1, -1, 0, 0, 1, 1, -1, -1]
dy = [0, 0, 1, -1, 1, -1, 1, -1]

# 알고리즘 Bfs
def Bfs(num, x, y):
    # deque 선언
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w:
                if num[nx][ny] == 1:
                    # 다음 탐색과 겹치지 않기 위해 해당 조건 칸의 숫자를 변경
                    num[nx][ny] = 0
                    q.append((nx, ny))
            else:
                continue


while True:
    w, h = map(int, sys.stdin.readline().split())
    count = 0
    num = []
    if w == 0 and h == 0:
        break
    for _ in range(h):
        num.append(list(map(int, sys.stdin.readline().split())))
    for i in range(h):
        for j in range(w):
            if num[i][j] == 1:
                count += 1
                Bfs(num, i, j)
    print(count)

 

 

 보충할 점

• DFS 재귀 활용 미숙