[Problem Solving] 백준 4963 섬의 개수

섬의 개수 문제는 다음의 링크를 확인해주시기 바랍니다. 문제 해설

4963번: 섬의 개수

지도가 주어지면 해당 지도에 섬이 몇 개 인지 찾는 문제로 그래프 탐색 이론을 활용하여 해결할 수 있습니다. 다음은 문제 해결 순서입니다.

 

1. w, h를 입력받는다.
2. 둘의 값이 0이 아니라면 반복문을 돌면서 땅을 찾는다.
3. 아직 방문하지 않은 땅을 찾았다면 섬의 개수를 1 증가시켜준다.
4. 땅을 방문 처리 해준 후 bfs 탐색을 실행시킨다.
5. 1을 반복한다.

지도에서 땅을 찾아 bfs 알고리즘을 실행시키는 것은 해당 땅을 포함한 섬의 크기만큼을 지도에서 방문 처리해주기 위해서입니다. 이렇게 처리를 하면 같은 섬의 다른 땅을 찾았을 경우 이미 방문 처리가 되어 있기 때문에 섬의 크기를 증가시키지 않고, 다른 땅을 찾게 됩니다.

 

다음은 해결 순서를 코드로 구현한 부분입니다.

 

from collections import deque

def bfs(x, y):
  queue = deque()
  queue.append((x,y))
  visited[x][y] = True

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

  while queue:
    x, y = queue.popleft()
    
    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0 <= nx < m and 0 <= ny < n:
        if not visited[nx][ny] and data[nx][ny] == 1: 
          queue.append((nx, ny))
          visited[nx][ny] = True

def solution(n, m):
  answer = 0
  for i in range(m):
    for j in range(n):
      if data[i][j] == 1 and visited[i][j] == False: 
        bfs(i, j)
        answer += 1
  return answer

while True:
  n, m = map(int, input().split())
  visited = [[False] * n for _ in range(m)]
  data = []

  if n == 0 and m == 0:
    break
    
  for _ in range(m):
    data.append(list(map(int, input().split())))

  print(solution(n, m))

 

위의 코드는 3가지 부분으로 나누어져 있습니다. 다음은 3가지 부분을 순서대로 개념만 작성한 것입니다. 코드를 이해할 때 도움이 될 것입니다.

• bfs 알고리즘: def bfs 부분
• 정답 계산: def solution 부분
• 변수 입력: 나머지 부분

해당 문제는 8가지 방향에 대한 탐색을 진행해야 합니다. 따라서 다음과 같이 구현하는 것으로 문제를 해결하였습니다.

 

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

 

해당 문제는 일반적인 그래프 탐색 이론 문제와는 다르게 상, 하, 좌, 우뿐만 아니라 각 방향의 대각선으로 이동할 수 있다는 차이점이 있어 새롭게 다가갈 수 있었던 유형의 문제였습니다.