[Baekjoon4963] 섬의 개수 python

문제 4963

python 최대 깊이는 1000이기 때문에 runtime error 발생.

import sys
sys.setrecursionlimit(10**7)

DFS 코드

import sys
sys.setrecursionlimit(10**7)

def dfs(x, y):
	# 방문하면 0으로 저장
    board[x][y] = 0
    # 위,아래,왼,오, 대각선 4번으로 검사
    for i in range(8):
        a = x+dx[i]
        b = y+dy[i]
		
        # 검사할 위치가 지도 내부이며 그 값이 1
        if 0<= a <h and 0<= b <w:
            if board[a][b]==1:
                dfs(a,b)

# 가로, 세로, 대각선 이동
dx = [0,1,1,1,0,-1,-1,-1]
dy = [1,1,0,-1,-1,-1,0,1]

# 0 0 이 나올 때까지 반복
while True:
    w, h = map(int, input().split())
    if w==0 and h==0:
        break
    
    board = [] # 지도
    answer = 0 # 섬의 개수

    for _ in range(h):
        board.append(list(map(int, input().split())))

	# board의 값이 1이면 dfs 실행하고 연결된 1을 모두 찾으면 answer++
    for i in range(h):
        for j in range(w):
            if board[i][j]==1:
                dfs(i,j)
                answer+=1

    print(answer)

BFS 코드

from collections import deque

def bfs(x, y):
	# 방문하면 0으로 저장
    board[x][y] = 0
    # 큐에 첫 위치 삽입
    queue = deque()
    queue.append((x,y))

	# 큐가 빌 때까지 반복
    while queue:
        a, b = queue.popleft()
        for i in range(8):
            nx = a+dx[i]
            ny = b+dy[i]

            if 0<= nx <h and 0<= ny <w:
                if board[nx][ny]==1:
                    queue.append((nx,ny))
                    board[nx][ny] = 0

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

w, h = map(int, input().split())
board = []
answer = 0

for _ in range(h):
    board.append(list(map(int, input().split())))

for i in range(h):
    for j in range(w):
        if board[i][j]==1:
            bfs(i,j)
            answer+=1

print(answer)

위: BFS
아래: DFS