백준 알고리즘 4963번: 섬의 개수(Python)

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

4963번: 섬의 개수

---

문제 해결을 위한 과정

이 문제의 경우 일반적인 상, 하, 좌, 우 네가지 방향을 탐색하는 bfs 문제에서 조금 벗어난 대각선까지 포함하는 8가지 방향을 탐색해야 하는 문제 입니다. 

일반적인 네가지 방향의 경우와 달리 여덟가지 방향을 그림으로 표현하면 다음과 같습니다.

따라서 dx, dy 리스트를 다음과 같이 만들고 for i in range(8)로 반복하면 됩니다.

 

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

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

---

소스코드

from collections import deque
 
def bfs(graph, visited, i, j):
  q = deque()
  q.append((i, j))
  visited[i][j] = 1
  while q:
    x, y = q.popleft()
    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or ny < 0 or nx >= n or ny >= m:
        continue
      if graph[nx][ny] == 1 and visited[nx][ny] == 0:
        visited[nx][ny] = 1
        q.append((nx, ny))
      
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]  
while True:
  m, n = map(int, input().split())
  if m == 0 and n == 0:
    break
  graph = []
  for _ in range(n):
    graph.append(list(map(int, input().split())))
  visited = [[0] * m for _ in range(n)]
 
  count = 0
  for i in range(n):
    for j in range(m):
      if graph[i][j] == 1 and visited[i][j] == 0:
        bfs(graph, visited, i, j) 
        count += 1
  print(count)