티스토리 뷰

개발자를 위한 한 걸음/코딩 문제

섬의 개수 - 백준 #4963, 실버2, 그래프/bfs/dfs

혯딩 2023. 4. 16. 11:25

문제 링크

 

4963번: 섬의 개수

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

www.acmicpc.net

풀이

1.  너비 우선 탐색(bfs)

from sys import stdin
from collections import deque

def bfs(x, y, w, h, grid, visited):
    queue = deque([(x, y)])
    visited[x][y] = True

    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    while queue:
        cx, cy = queue.popleft()
        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < h and 0 <= ny < w and not visited[nx][ny] and grid[nx][ny] == 1:
                queue.append((nx, ny))
                visited[nx][ny] = True

def count_islands(w, h, grid):
    visited = [[False] * w for _ in range(h)]
    count = 0

    for x in range(h):
        for y in range(w):
            if not visited[x][y] and grid[x][y] == 1:
                bfs(x, y, w, h, grid, visited)
                count += 1

    return count

def main():
    while True:
        w, h = map(int, stdin.readline().split())
        if w == 0 and h == 0:
            break

        grid = [list(map(int, stdin.readline().split())) for _ in range(h)]
        print(count_islands(w, h, grid))

if __name__ == "__main__":
    main()

2. 깊이 우선 탐색(dfs)

from sys import stdin
import sys
sys.setrecursionlimit(10**5)

def dfs(x, y, w, h, grid, visited):
    if x < 0 or x >= h or y < 0 or y >= w:
        return
    if visited[x][y] or grid[x][y] == 0:
        return

    visited[x][y] = True

    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        dfs(nx, ny, w, h, grid, visited)

def count_islands(w, h, grid):
    visited = [[False] * w for _ in range(h)]
    count = 0

    for x in range(h):
        for y in range(w):
            if not visited[x][y] and grid[x][y] == 1:
                dfs(x, y, w, h, grid, visited)
                count += 1

    return count

def main():
    while True:
        w, h = map(int, stdin.readline().split())
        if w == 0 and h == 0:
            break

        grid = [list(map(int, stdin.readline().split())) for _ in range(h)]
        print(count_islands(w, h, grid))

if __name__ == "__main__":
    main()
저작자표시 비영리 (새창열림)

'개발자를 위한 한 걸음 > 코딩 문제' 카테고리의 다른 글

구름스퀘어 - 구름, 난이도2, 그리디  (0) 2023.04.28
그래프 탐색 - 백준 #14217, 골드5, 그래프/너비 우선 탐색  (0) 2023.04.28
수식 최대화 - 프로그래머스 lv.2  (0) 2023.04.14
톱니바퀴 - 백준 #14891, 골드5, 구현/시뮬레이션  (0) 2023.04.14
괄호 변환 - 프로그래머스 lv.2  (0) 2023.04.14