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

[python] 백준 4963 : 섬의 개수

4963번: 섬의 개수 (acmicpc.net)

4963번: 섬의 개수

실버 2

그래프, DFS, BFS

---

접근 

좌표를 이동하면서 bfs를 탐색하는 문제를 풀어봤다면 쉽게 풀 수 있는 문제이다.

1은 땅이고 0은 바다이므로, 1을 찾아낼 때 덱에 값을 넣고, 1을 0으로 바꿔 방문처리를 한다.

 

탐색이 끊기면 사면이 바다인 것이므로 섬의 개수를 카운트하도록 한다.

 

코드

import sys; input = sys.stdin.readline
from collections import deque

def bfs(x, y):
	# 네 방향과 대각선, 총 8방향으로 이동하기 위한 리스트
    dx = [1, -1, 0, 0, 1, -1, 1, -1]
    dy = [0, 0, -1, 1, -1, 1, 1, -1]
    queue = deque()
    queue.append([x, y])  # 좌표를 큐에 넣는다.

    while queue:
        x, y = queue.popleft()
        for i in range(8):
            ndx = x + dx[i]    # 이동할 좌표 설정
            ndy = y + dy[i]
            if 0 <= ndx < h and 0 <= ndy < w and map_lst[ndx][ndy] == '1':
                map_lst[ndx][ndy] = '0'    # 조건에 만족하면 땅을 바다로 만드는 방법으로 방문처리
                queue.append([ndx, ndy])

    
while True:
    w, h = map(int, input().split())
    if w == h == 0:
        break
    land = 0
    map_lst = [input().split() for i in range(h)]

    for i in range(h):
        for j in range(w):
            if map_lst[i][j] == '1':
                bfs(i, j)
                land += 1    # 남아있는 땅이 8방향 안에 없으면 bfs 함수를 빠져나오므로 섬의 개수를 카운트
    print(land)