[백준] 4963번 - 섬의 개수

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

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

다음과 같이 예제 입력이 주어졌을 때,

상하좌우 및 대각으로 이루어진 1을 섬이라고 보기 때문에

0 1 1 3 1 9 (줄바꿈해서) 에 대한 출력이 나와야한다.

 

(-1, -1)	(-1, 0)	(-1, 1)
(0, -1)	기준점	(0, 1)
(1, -1)	(1, 0)	(1, 1)

 

상하좌우를 기준으로 하던 기존 그래프 탐색과 다르게

대각선 4가지의 꼭짓점도 탐색해야하기 때문에 8번의 반복문을 돌아야한다.

 

그리고 섬은 대각선으로 이어진 1을 깊이 탐색하면서

방문 여부를 체크하고, 다 마친 dfs 탐색이 존재하면

섬의 갯수를 1씩 늘려가면서 세어주는 방식으로 코드를 작성하였다.

 

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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)]
  chk = [[False] * w for _ in range(h)]
  cnt = 0

  dy = [0, 1, 1, 1, 0, -1, -1, -1]
  dx = [1, 1, 0, -1, -1, -1, 0, 1]
  
  def dfs(y, x):
    for k in range(8):
      ny = y + dy[k]
      nx = x + dx[k]
      if 0 <= ny < h and 0 <= nx < w:
        if graph[ny][nx] == 1 and chk[ny][nx] == False:
          chk[ny][nx] = True
          dfs(ny, nx)

  for i in range(h):
    for j in range(w):
      if graph[i][j] == 1 and chk[i][j] == False:
        chk[i][j] = True
        dfs(i, j)
        cnt += 1
  print(cnt)

 

재귀의 깊이를 모르기 때문에

sys.setrecursionlimit() 함수로 재귀의 수를 수동 설정해주어야만

RecursionError 오류를 만나지 않을 수 있다.

 

화이팅 💪