[BOJ] 4963 섬의 개수

태환·2024년 3월 12일
0

Coding Test

목록 보기
101/151

📌 [BOJ] 4963 섬의 개수

📖 문제

📖 예제

📖 풀이

from collections import deque

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

def BFS(x, y):
  queue = deque()
  queue.append([x,y])
  while queue:
    x, y = queue.popleft()
    for i in range(8):
      nx=x+dx[i]
      ny=y+dy[i]
      if 0<=nx<h and 0<=ny<w and graph[nx][ny] == 1:
        graph[nx][ny] = 0
        queue.append([nx, ny])

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

BFS/DFS 두 방법을 통해 다음 문제를 해결할 수 있다.

profile
연세대학교 컴퓨터과학과 석사 과정

0개의 댓글