[백준/알고리즘]#4963: 섬의 개수 [파이썬(python)/그래프/DFS/BFS]

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

4963번: 섬의 개수

 

https://hidemasa.tistory.com/136

[백준/알고리즘]#1303: 전쟁-전투 [파이썬(python)/그래프/DFS/BFS]

전에 풀이한 문제와 비슷한 풀이의 DFS/BFS 그래프 문제다.

각 기준점에서부터의 거리를 계산하는 그래프 풀이 문제인데, x,y 상하좌우 방향 뿐 아니라 대각선 방향까지 고려핸다는 점이 추가되었다.

 

파이썬 코드 

#4963_섬의개수
import sys
from collections import deque 
input = sys.stdin.readline

#direction in mapp
dx = [1,-1,0,0,1,-1,1,-1] #right, left, up, down, diag(") 
dy = [0,0,-1,1,-1,1,1,-1]

def bfs(x,y):
    mapp[x][y]=0
    q=deque()
    q.append([x,y])
    while q:
        a,b = q.popleft()
        for i in range(8):
            nx = a + dx[i]
            ny = b + dy[i]
            if 0 <= nx < h and 0 <= ny < w and mapp[nx][ny]==1:
                mapp[nx][ny]=0
                q.append([nx,ny])


while(1):
    w, h = map(int, input().split())
    if w==0 and h==0:
        break
    mapp = []
    cnt=0
    for _ in range(h):
        mapp.append(list(map(int, input().split())))
    for i in range(h):
        for j in range(w):
            if mapp[i][j] == 1:
                bfs(i,j)
                cnt+=1

    print(cnt)

이와 비슷한 문제로는

#2667: 단지번호 붙이기

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

 

#4963: 섬의 개수

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

가 있다.