[Python] 4963번 섬의 개수 / DFS.ver

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

 

이전에 재귀로 풀었던 함수를 이번에는 스택을 사용하여 풀어보았다.

2025.04.08 - [coding test/백준] - [Python] 4963번 섬의 개수 / 재귀함수.ver

# dfs-stack
dx=[-1,-1,-1,0,0,1,1,1]
dy=[1,0,-1,1,-1,1,0,-1]

def dfs(y,x):
    board[y][x]=0 #방문처리

    stack=[[y,x]]
    while stack:
        s=stack.pop()

        for i in range(8):
            ny=s[0]+dy[i]
            nx=s[1]+dx[i]
            if 0<=ny<h and 0<=nx<w:
                if board[ny][nx]==1:
                    board[ny][nx]=0
                    stack.append([ny,nx])

# 1. 입력값 받기
while True:
    w,h=map(int,input().split())

    if w==0 and h==0:
        break
    
    board=[list(map(int,input().split())) for _ in range(h)]

    # 2. 자료형 준비 

    # 탐색시작
    cnt=0
    for i in range(h):
        for j in range(w):
            if board[i][j]==1:
                # 3. dfs-stack
                dfs(i,j) 
                cnt+=1

    # 4. 정답 출력
    print(cnt)

 

재귀로 하였을 때보다 시간이 빨라진 것을 볼 수 있었다.