알고리즘/백준 문제풀이

[boj] 백준 4963 섬의 개수 python 풀이

감자156 2023. 5. 18. 12:29
반응형

풀이

bfs로 풀이함

 

문제

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

 

4963번: 섬의 개수

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도

www.acmicpc.net

 

코드

import sys
input = sys.stdin.readline

move = {(-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1)}

def bfs(MAP, x, y):
    q = [(x,y)]
    MAP[x][y] = -1
    while q:
        x,y = q.pop(0)

        for tx, ty in move:
            nx = x + tx
            ny = y + ty

            if 0<=nx<h and 0<=ny<w and MAP[nx][ny] == 1:
                q.append((nx,ny))
                MAP[nx][ny] = -1 # visited

    
while True:
    w,h = map(int,input().split())
    if w==0 and h == 0:
        break

    MAP = [list(map(int,input().split())) for _ in range(h)]
    cnt = 0

    for i in range(h):
        for j in range(w):
            if MAP[i][j] == 1:
                bfs(MAP, i, j)
                cnt += 1
    print(cnt)
반응형