[백준 4963번] 섬의 개수

count_list = []

def dfs(x,y,area,visited):

  if area[x][y] == 0 or visited[x][y]:
    return False

  visited[x][y] = True

  nx = [-1,1,-0,0,-1,-1,1,1]
  ny = [0,0,-1,1,-1,1,-1,1]

  for i in range(8):
    temp_x = x + nx[i]
    temp_y = y + ny[i]

    if temp_x >=0 and temp_x < n and temp_y >= 0 and temp_y < m:
      if not visited[temp_x][temp_y] and area[temp_x][temp_y] == 1:
        dfs(temp_x,temp_y,area,visited)

  return True

while True:
  m, n = map(int,input().split())

  count = 0

  if n == 0 and m == 0:
    break

  area = []
  visited = [[False]*m for _ in range(n)]

  for _ in range(n):
    area.append(list(map(int,input().split())))

  for i in range(n):
    for j in range(m):
      if dfs(i,j,area,visited):
        count += 1

  count_list.append(count)

for i in count_list:
  print(i)

이번 문제는 여지껏 봐왔던 탐색 문제와는 조금 다른 유형이었다.

 

왜냐하면 2차원 배열에서 인접하거나 이동할 수 있는 영역의 기준은 '상-하-좌-우' 뿐이었지만, 이번 문제는 대각선으로도 이동할 수 있다는 조건이 있었기 때문이다.

 

nx = [-1,1,-0,0,-1,-1,1,1]
ny = [0,0,-1,1,-1,1,-1,1]

이는 평소에 상하좌우로 움직이기 위해 사용했던 nx와 ny의 범위를 늘려 대각선까지 체크할 수 있도록 해주면 되었다 😎

 

또한 하나의 테스트케이스만 주어지는 것이 아니라 반복적으로 테스트케이스를 입력할 수 있기 때문에 while(True)문으로 처리해주어야 한다는 점도 존재했다.

 

각 테스트케이스 마다 입력되는 배열(area)와 방문여부 배열(visited)가 새로 업데이트 되어야 하기 때문에 전역으로 선언해주고 푼다면 문제가 잘못 풀이된다는 점 또한 배울 수 있었다 :)