[백준] 4963번 섬의 개수 파이썬

BFS 문제로 간다...!!!

 

4963번 섬의 개수 풀이

[시도1] 맞았습니다!! with 솔루션

from collections import deque

def bfs(x, y):

  queue = deque()
  queue.append((x,y))
  
  ground[x][y] = 0

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

  while queue:
    position = queue.popleft()
    for i in range(8):
      nx = position[0] + dx[i]
      ny = position[1] + dy[i]
      
      if 0 <= nx < h and 0 <= ny < w:
        if ground[nx][ny] == 1:
          ground[nx][ny] = 0
          queue.append((nx,ny))

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

  for _ in range(h): 
    line = list(map(int, input().split())) 
    ground.append(line)
  
  for i in range(h): 
    for j in range(w): 
      if ground[i][j] != 0: 
        result += 1 
        bfs(i, j)
    
  print(result)

bfs는 큐를 사용하므로 deque를 import해준다. while 문에서는 전체적인 코드 흐름을 볼 수 있다. 입력 받은 w와 h가 모두 0일 때에는 프로그램이 종료하고 그렇지 않다면 프로그램이 작동하는데 ground에 입력값을 넣어 전체 섬과 바다가 입력된 지도를 만들 수 있다. 지도에서 한 지점이 0이 아닐 때 즉, 1일 때는 섬이므로 결과 값에 1을 더한 뒤 bfs를 다시 호출한다. 호출된 bfs에서는 현재 위치에서 상하좌우대각선 방향들을 고려하여 연결된 섬의 유무를 확인한다. queue에서 popleft하여 꺼낸 값이 현 위치이고 이동한 위치는 nx와 ny로 표현할 수 있기에 ground[nx][ny]가 1이면 다시 방문하지 않도록 0으로 바꾸준 뒤 queue에 추가한다. queue에 있는 모든 위치를 다 확인하였다면 해당 테스트 케이스가 완료된다.

 

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

4963번: 섬의 개수