[백준 알고리즘/Python] 4963 섬의 개수

문제

 

 

문제 이해

2차원 배열에서 상하좌우, 대각선을 고려해서 1이면 다른 1을 찾을 수 있게끔 합니다. 1을 찾는다면 0으로 만들어서 다시 검색이 안되도록 만듭니다.

 

코드

import sys
sys.setrecursionlimit(10**6)

def dfs(x,y):

    #주어진 범위를 벗어나면 종료
    if(x <= -1 or x >= h or y <= -1 or y >= w):
        return False

    if(graph[x][y] == 0):
        return False

    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    if(graph[x][y] == 1):
        graph[x][y] = 0
        dfs(x-1,y-1) #왼쪽 위 대각선
        dfs(x-1,y)   # 상
        dfs(x-1,y+1) #오른쪽 위 대각선

        dfs(x,y-1)   #왼쪽
        dfs(x,y+1)   #오른쪽

        dfs(x+1,y-1) #왼쪽 아래 대각선
        dfs(x+1,y)   #아래
        dfs(x+1,y+1) #오른쪽 아래 대각선
        return True



while(True):
    w, h  = map(int,input().split())

    if(w==0 and h==0):
        break

    #2차원 배열 만들기
    graph = []
    for i in range(h):
        graph.append(list(map(int,input().split())))

    
    result = 0

    #정의된 DFS 함수 호출
    for i in range(h):
        for j in range(w):
            if(dfs(i,j) == True):
                result += 1
    print(result)

만약 섬이 있다면(=1) 주변에 있는 섬을 스택으로 삼을 것입니다. 그리고 자신은 0으로 만듭니다.

주변의 1을 계속 찾다가 결국 스택에 맨 아래있는 것이 True 한번만 반환하게 됩니다.

즉 1을 1번 찾으면 dfs로 꼬리잡기하듯이 모두 0으로 만듭니다. 그리고 그 과정을 count하기 위해 맨 마지막을 의미있게 True로 만든 것입니다.