[Baekjoon] 4963번 : 섬의 개수 (Python, 그래프, DFS, BFS)

[Baekjoon] 4963번 : 섬의 개수 (Python, 그래프, DFS, BFS)

 

목차

 

 

 

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

4963번: 섬의 개수

 

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 33136KB / 시간 92ms / 코드 길이 646B

 

DFS, BFS를 활용한 그래프 문제이다.

섬의 개수를 세는 것으로 이를 위한 그래프 list, 방문처리를 위한 value 값 설정 등으로 진행한다.

다만 대각선이 있다는 점도 유의해야 한다.

또한 Recursion Error 런타임 에러가 날 수 있으므로 sys.setrecursionlimit 또한 설정해야 한다.

여기서는 DFS만을 활용하도록 하겠다.

 

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

dx = [-1,1,0,0,-1,-1,1,1]
dy = [0,0,-1,1,-1,1,-1,1]

def dfs(x, y, w, h):
    island[x][y] = 2
    for k in range(8):
        nx, ny = x + dx[k], y+dy[k]
        if 0 <= nx < h and 0 <= ny < w:
            if island[nx][ny] == 1:
                dfs(nx, ny, w, h)
    return 1

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

 

방법 2 - 메모리 32436KB / 시간 108ms / 코드 길이 765B

 

BFS를 활용하여 푼 그래프 문제이다.

 

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

dx = [-1,1,0,0,-1,-1,1,1]
dy = [0,0,-1,1,-1,1,-1,1]

def bfs(x, y, w, h):

    q = deque()
    q.append((x,y))
    island[x][y] = 2

    while q:
        cx, cy = q.popleft()
        for k in range(8):
            nx, ny = cx + dx[k], cy+dy[k]
            if 0 <= nx < h and 0 <= ny < w and island[nx][ny] == 1:
                island[nx][ny] = 2
                q.append((nx, ny))
    return 1

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