[백준/4963/파이썬] 섬의 개수

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

4963번: 섬의 개수

Problem

• 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.
• 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

조건

• 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.
• 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.
• 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.
• 입력의 마지막 줄에는 0이 두 개 주어진다.

SOL

연결요소를 찾는 간단한 문제이다. BFS로 연결요소를 찾아줬다. 

Input이 충분히 작기 때문에, 가능하다!

import sys
from collections import deque
input= sys.stdin.readline
dx=[0,1,0,-1,1,1,-1,-1]
dy=[1,0,-1,0,1,-1,1,-1]
def bfs(y,x):
    dq=deque()
    dq.append((y,x))
    visited[y][x] = True
    while dq:
        y,x= dq.popleft()
        for k in range(8):
            ny=y+dy[k]
            nx=x+dx[k]
            if not (0<=ny<N and 0<=nx<M):
                continue
            if board[ny][nx] ==1 and not visited[ny][nx]:
                visited[ny][nx] = 1
                dq.append((ny,nx))


while True:
    M,N=map(int,input().split())
    if N==0 and M==0:
        break
    board=[list(map(int,input().split())) for _ in range(N)]
    visited=[[0 for _ in range(M)] for _ in range(N)]
    cnt=0
    for i in range(N):
        for j in range(M):
            if board[i][j]==1 and not visited[i][j]:
                bfs(i,j)
                cnt+=1
    print(cnt)