[백준]4963번: 섬의 개수

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

4963번: 섬의 개수

---

dfs로 풀었더니 RecursionError가 나서.. 이유를 찾아보니까

BOJ 채점 서비스에서는 파이썬 최대 재귀 깊이가 1000으로 설정되어 있다고 한다.

그러니깐 테케중에서 재귀를 1000번 이상 수행하는 게 있었나보다

 

\해결법은 여러 가지가 있는데 그중에서 젤 쉬운거 선택함 ^v^

import sys
sys.setrecursionlimit(10**6)

최대재귀깊이를 임의로 겁나 큰 수로 설정해주면 끝!

---

import sys
sys.setrecursionlimit(10**6)

#상하좌우대각선
dx = [-1, -1, -1, 0, 1, 1, 1, 0]
dy = [-1, 0, 1, 1, 1, 0, -1, -1]


def dfs(x, y):
  #범위를 벗어나지 않으면서 방문한 적 없으면
  if 0 <= x < w and 0 <= y < h and graph[x][y] == 1:
    graph[x][y] = 0  # 방문 처리

    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]
      dfs(nx, ny)
    return True #섬의 land요소들 중 최초로 방문하는 점만 True를 리턴
  return False


while True:
  #h,w,그래프 정보 입력받기
  h, w = map(int, input().split())
  if w == 0 and h == 0:
    break

  graph = []
  for i in range(w):
    graph.append(list(map(int, input().split())))

  #섬의 개수 count
  cnt = 0
  for i in range(w):
    for j in range(h):
      if dfs(i, j) == True: #최초 방문 칸에서에만 cnt를 증가시켜줌
        cnt += 1

  print(cnt)

보통 행, 열 순서로 입력받는 게 많은데 이 문제는 열, 행 순으로 입력받더랑

---

약간 찝찝해서 재귀를 아예 사용하지 않는 bfs로도 풀어봤다

from collections import deque


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

def bfs(x,y):
  if graph[x][y]==0: #이미 방문한 적 있으면 false리턴
    return False
    
  graph[x][y]=0 #방문 처리
  q=deque()
  q.append((x,y))

  while q:
    a,b=q.popleft()
    for i in range(8):
      nx = a + dx[i]
      ny = b + dy[i]
      if 0<=nx<w and 0<=ny<h and graph[nx][ny]==1:
        graph[nx][ny]=0
        q.append((nx,ny))
  return True #인접한 칸들 모두 방문이 끝나면 true리턴



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

  graph = []
  for i in range(w):
    graph.append(list(map(int, input().split())))

  cnt = 0
  for i in range(w):
    for j in range(h):
      if bfs(i, j) == True:
        cnt += 1

  print(cnt)