[백준 4963번] 섬의 개수 (Python/파이썬)

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

4963번: 섬의 개수

평범한 그래프 탐색문제이다. 

DFS를 사용해도 좋고, BFS를 사용해도 좋다.

본인은 BFS를 사용하여 각 섬의 개수를 탐색하였다.

차이점라고 하기에도 뭐하지만 굳이 뽑자면, 대각선에 있는 섬도 연결되어있는 섬으로 보기 때문에 현재 좌표를 기준으로 주위에 있는 모든 방향(8방향)을 모두 탐색해야한다.

그래프 문제 푼지 오래된거 같아서 오랜만에 간단히 하나 풀었다.

코드는 다음과 같다.

 

import sys
from collections import deque
input = sys.stdin.readline
dx = [1,0,-1,0,1,-1,1,-1]
dy = [0,1,0,-1,-1,1,1,-1]

def BFS(i,j):
  queue = deque([])
  queue.append((i,j))
  while queue:
    (x,y) = queue.popleft()
    for i in range(8):
      tmp_x = x + dx[i]
      tmp_y = y + dy[i]
      if 0 <= tmp_x < h and 0 <= tmp_y < w:
        if not visited[tmp_x][tmp_y] and island[tmp_x][tmp_y] == 1:
          queue.append((tmp_x,tmp_y))
          visited[tmp_x][tmp_y] = True

while True:
  w, h = map(int,input().split())
  if w == 0 and h == 0:
    sys.exit()
  island = []
  for _ in range(h):
    island.append(list(map(int,input().split())))
  visited = [[False for _ in range(w)] for _ in range(h)]
  cnt = 0

  for i in range(h):
    for j in range(w):
      if island[i][j] == 1 and not visited[i][j]:
        visited[i][j] = True
        BFS(i,j)
        cnt += 1
  print(cnt)