[백준 4963] 섬의 개수 (python)

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

4963번: 섬의 개수

처음에 이 문제를 접했을때 dfs를 사용하려 마음 먹었다. 

 

1. 스택에 정점의 인덱스 값을 넣고 visit_check 함수에 들어간다.

2. 스택에 값을 팝하면서 변수 i,j에 정점의 인덱스를 저장한다.

3. i,j의 값이 리스트 범위를 넘어가는 곳이거나, 방문했던 곳이면 해당 값을 버리고 스택에서 다시 값을 꺼낸다.

4. 스택의 값이 모두 비었다면 다시 돌아와서 isl 변수에 1을 더한다. 처음 스택에 넣었던 정점으로 부터 만들어진 섬이 하나 생긴 것이다.

5. 1부터 반복해서 섬의 갯수를 구한다.

 

 

 

import sys
from collections import deque
 
def dfs(stack,li,visited):
    while stack:
        tmp = stack.pop()
        i = tmp[0]
        j = tmp[1]
        if i < 0 or j < 0 or i > len(li)-1 or j > len(li[0])-1:
            continue
        if li[i][j] == 0 or visited[i][j]:
            continue
 
        visited[i][j] = 1
 
        stack.append([i-1,j])
        stack.append([i-1,j+1])
        stack.append([i,j+1])
        stack.append([i+1,j+1])
        stack.append([i+1,j])
        stack.append([i+1,j-1])
        stack.append([i,j-1])
        stack.append([i-1,j-1])
 
 
stack = deque()
island = []
while True:
    a, b = map(int, sys.stdin.readline().split())
    if a == 0 and b == 0:
        break
    li = []
    for _ in range(b):
        li.append(list(map(int, sys.stdin.readline().split())))
    visited = []
    for i in range(len(li)):
        tmp = [0 for j in range(len(li[0]))]
        visited.append(tmp)
    isl = 0
 
    for i in range(len(li)):
        for j in range(len(li[0])):
            if visited[i][j] == 1:
                continue
            if li[i][j] == 0:
                continue
            stack.append([i,j])
            dfs(stack,li,visited)
            isl+=1
    island.append(isl)
 
for i in range(len(island)):
    print(island[i])