[백준] 4963번 섬의 개수 - BFS 풀이 (Python3)

문제와 입출력 조건

제한 조건과 설계

1. W와 H는 50보다 작다. -> MAX 2500 그래프 

2. DFS로 2000번 이상 탐색 시 Recursion Error 발생될 수 있기에 BFS 선택

3. 시간 제한 1초, 메모리 제한 128MB -> 엄격한 제한이므로 Queue 방문 처리 필수

---

자연어 알고리즘과 코드

1. 그래프 입력을 받는다.

2. 그래프를 BFS로 탐색한다.

• 탐색 지점이 0 이면 -> continue
• 탐색 지점이 1 이면 -> 그 지점을 시작 지점으로 삼아 queue에 enqueue하고 BFS 탐색을 시작
  • land를 1증가시킨다. Queue에서 dequeue 한다.
  • for문을 이용해 dequeue 된 지점에서 상,하,좌,우 + 왼쪽 위 대각선, 왼쪽 아래 대각선, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 이동한다.
    • 이동한 지점의 값이 그래프 범위 밖이면 -> continue
    • 이동한 지점의 값이 0(바다)이면 -> continue
    • 이동한 지점의 값이 1(육지)이면 -> 그 지점을 queue에 넣고 0으로 방문 처리한다.
  • qeueue가 빌 때까지 위의 과정을 반복

3. 2번을 마치고 land를 리턴한 후 land를 출력한다.

4. 0이 입력 될 때 까지 위의 과정을 1~3 과정을 반복한다.

import sys
from collections import deque

input = sys.stdin.readline

def bfs(len_w, len_h, graph):
    queue = deque()
    # 상,하,좌,우 + 왼쪽 위 대각선, 왼쪽 아래 대각선, 오른쪽 위 대각선, 오른쪽 아래 대각선
    dh = [-1,1,0,0] + [-1,1,-1,1]
    dw = [0,0,-1,1] + [-1,-1,1,1]
    land = 0
    for i in range(len_h):
        for j in range(len_w):

            if graph[i][j] == 1:
                land += 1
                queue = deque()
                queue.append((j,i)) # w,h
                while queue:
                    w,h = queue.popleft()
                    for k in range(8):
                        nh = h + dh[k]
                        nw = w + dw[k]
                        
                        if nw < 0 or nh < 0 or nw >= len_w or nh >= len_h:
                            continue

                        if graph[nh][nw] == 0:
                            continue
                        
                        queue.append((nw,nh))
                        graph[nh][nw] = 0

    return land

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

    for i in range(h):
        graph.append(list(map(int, input().split())))
    print(bfs(w,h,graph))

 

---

세 줄 요약

1. 상, 하, 좌, 우 이동에서 대각선 이동까지 확장한 문제.
2. w,h로 받았으면 쭉 w,h 순으로 다루자(append, popleft 등 할때).
3. graph만 graph[h][w]로 다루면 된다.

(방문 처리 잘 했군.. ㅋㅋ)