[응용] DFS와 2차원 배열 내 영역의 최대 개수 구하기

 

1. 개요

DFS 알고리즘을 적용한 문제 유형으로 2차원 배열에 포함된 특정 영역의 최대 개수를 구하는 문제가 많이 출제된다.

아래 두 문제를 풀어보며 이러한 문제 유형에 대해 이해하게 되어, 그 내용을 정리해보려고 한다.

 

이 글에서는 내가 이해한 개념을 자세하게 풀어서 정리하고, 관련 문제의 코드도 함께 살펴 볼 예정이다.

 

 

단, 이 글은 DFS 알고리즘에 대해 이해하고 있다는 가정 하에 설명을 진행한다.

만약 DFS 알고리즘의 개념이나 원리를 잘 모른다면 아래 글을 참고하기를 추천한다.

https://developer-zoyh.tistory.com/17

[알고리즘] DFS(Depth-First Search)와 BFS(Breadth-First Search)

 

 

 

2. 관련 문제

DFS 개념을 이해하고 있는 사람이라면 아래 설명을 읽기 전에 먼저 문제를 풀어보는 것을 추천한다.

(도전해 보신 후 댓글로 추가 의견이나 조언 한 스푼 얹어주시면 감사하겠습니다 😄)

1. 안전 영역: https://www.acmicpc.net/problem/2468

2. 섬의 개수: https://www.acmicpc.net/problem/4963

 

 

3. 개념 설명

 

2차원 배열 예시

 

위와 같은 배열이 있다고 가정하자.

0이 바다, 1이 섬이라고 할 때, 우리는 이 그림을 보고 눈으로 총 2개의 섬이 존재함을 알 수 있다.

그러나 코드로는 어떻게 접근할 수 있을까? 이 때 사용할 수 있는 것이 "DFS" 이다.

 

DFS는 깊이 우선 탐색이므로 특정 노드를 중심으로 가장 깊이 위치한 노드까지 접근했다가 한칸씩 빠져나오며 인접 노드를 탐색한다.

즉, 기준 노드에서 가장 멀리 있는 노드까지 간 다음, 되돌아오면서 그 근처를 모두 둘러보고 온다는 의미이다.

 

이렇게 탐색을 마치고 나오면 처음 시작한 노드를 기준으로 영역 하나를 찾게 된다.

이 때, DFS를 통해 방문한 위치는 재방문 하지 않도록 별도 배열에 방문 여부 값을 저장해두어야 한다.

 

이 과정을 전체 배열에 반복해주면 영역의 개수를 구할 수 있게 된다.

 

2차원 배열에 DFS 적용 시 동작 순서

 

배열로 DFS 함수가 적용되는 위치를 나타내면 위 이미지와 같다.

 

1. 땅(1) 중에서 가장 앞에 있는 (0, 0) 위치에서 최초로 DFS 함수를 호출한다.

DFS 함수가 특정 위치에 호출되면 그 위치는 방문 처리된다. 따라서 DFS(0, 0)가 호출되면 (0, 0) 위치는 방문한 곳으로 처리된다.

아래에서는 내용이 반복되는 것을 방지하기 위해 DFS가 호출된 곳이 방문 처리가 된다는 내용은 생략하겠다.

 

2. DFS 함수 내에서 이동 가능한 방향(예: 상하좌우, 대각선)으로 DFS 함수를 호출하는데, 먼저 호출된 함수를 기준으로 실행된다.

위 이미지에서는 반시계 방향으로 호출된다는 가정 하에 작성하여 아래 위치인 DFS(1, 0)이 먼저 실행되었다.

 

3. (1, 0) 위치에서 더 이상 이동할 수 있는 땅(1)이 없으므로 스택에 저장되어 있던 기존 위치(0, 0)로 돌아간다.

 

4. (0, 0) 위치에서 이전에 방문하지 않았던 DFS(0, 1)이 실행된다. 마찬가지로 기존 위치는 스택에 저장된다.

 

5. (0, 2) 위치로 이동한 후 더 이상 이동할 수 있는 땅이 없으므로 이전 위치(0, 1)로 돌아가게 되고, 이전 위치에도 방문하지 않은 이동 가능한 땅이 더 이상 없으므로 더 이전의 위치(0, 0)으로 이동한다.

스택에 더 이상 이동할 수 있는 공간이 없고 근처에 방문하지 않은 위치도 존재하지 않는다.

이 경우, (0, 0) 지점을 시작으로 하는 영역 전체를 살펴보았다고 할 수 있으므로 영역 탐색을 종료한다.

 

이후 또 땅 위치에서 이 과정을 반복하면서 영역을 탐색하고, 영역 탐색이 종료될 때마다 1씩 개수를 더해준다.

그러면 배열 전체에 대해 탐색을 마쳤을 때 영역의 최대 개수를 구할 수 있게 된다.

 

 

4. 코드

이 코드는 위 관련 문제 중 안전 영역 문제에 대한 코드이다.

이 게시글에서는 DFS 접근 방식에 조금 더 집중하여 풀이를 정리한다.

 

참고로 각 문제의 해설은 문제마다 별도의 포스팅으로 정리해두었다. 필요한 사람은 아래 링크를 추가해두었으니 참고하면 좋을 것 같다.

 

def dfs(x, y, visited, w, h):
	'''
    파라미터 설명
    x: 현재 위치 중 x 좌표 
    y: 현재 위치 중 y 좌표
    visited: 방문 여부를 판단하는 배열 (True/False 값으로 채워져 있음)
    w: 이동 가능한 지도의 너비
    h: 이동 가능한 지도의 높이
    '''
	# 상하좌우, 대각선 모두 가능
    dirs = [[-1, -1], [-1, 0], [-1, 1],
            [0, -1], [0, 1],
            [1, -1], [1, 0], [1, 1]]
    
    visited[x][y] = True # 방문 처리
    
    # 인접 노드에 대해 DFS 함수 수행
    for d in dirs:
        nx, ny = x+d[0], y+d[1] # next step
        if nx < 0 or nx >= h or ny < 0 or ny >= w: continue # 배열을 벗어나는 경우 제외
        if not visited[nx][ny]:
            dfs(nx, ny, visited, w, h)

    return True
    

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0: break  # 정지 조건
    
    # 지도 입력 받기
    user_map = []
    for _ in range(h):
        user_map.append(input().split())
    
    # 지도 좌표 돌면서 Land일 때 dfs 함수 호출
    answer = 0
    visited = [[True if x == '0' else False for x in line] for line in user_map] # Sea는 방문 처리
    
    for x in range(h):
        for y in range(w):
            if not visited[x][y]:
                if dfs(x, y, visited, w, h): answer += 1
    
    # 정답 출력
    print(answer)

 

이 문제는 배열을 반복해서 받는 문제이기 때문에 While 문을 사용하여 입력을 받고 있다.

DFS 알고리즘과 관련 없는 부분이니 While 문 내부에 집중해서 보도록 하자.

 

1. 방문 여부 저장할 visited 배열 정의

지도를 입력 받은 후 visited라는 배열을 만들어 방문 여부 값을 저장한다.

이 때, Land(1)에 대해서만 방문하므로 어차피 방문하지 않는 Sea(0)는 visited 배열에 방문한 곳으로 처리하여, 혹시라도 방문될 가능성을 제거한다.

2. 방문하지 않은 Land에 대해 DFS 함수 실행

반복문을 돌면서 배열 전체의 방문하지 않은 Land에 대해 DFS 함수를 실행한다.

3. True 가 반환된 DFS에 대해 개수 카운팅

True가 반환된다는 것의 의미는 내부에서 인접 노드까지 모두 탐색을 완료하였다는 것을 의미한다. (구체적인 내용은 아래 참고)

즉, 반복문을 통해 처음 DFS를 호출한 위치(예: (0, 0))를 기준으로 한 영역 전체를 모두 탐색하였다는 것을 의미한다.

따라서 한 개의 영역에 대해 카운팅 처리를 해 주며, 이 때 visited 배열을 확인해보면 인접 노드가 방문처리 되어 있는 것을 확인할 수 있다.

4. 정답 출력

위 과정을 종료한 후 정답을 출력한다.

 

 

다음으로 DFS 함수 내부를 살펴보자. 해당 DFS 함수는 재귀 함수를 이용하여 구현되었다.

1. 인접 위치 (이동 방향) 정의

우선 이동 가능한 방향을 담은 dirs 배열이 정의되었다. 이 코드에서는 상하좌우 및 대각선까지 이동 가능하다.

만약 상하좌우만 이동 가능하다면 이 부분을 수정해주면 된다.

2. 방문 처리

visited 배열에 현재 위치를 True로 변경해주며 방문 처리를 수행해준다. 

3. 인접 노드 중 방문하지 않은 노드에 대해 DFS 함수 실행

재귀 함수가 너무 많이 호출되는 것을 방지하기 위해, 호출 전에 현재 위치가 배열에서 벗어나는 지 판단해준다.

벗어나지 않는 경우에 대해서만 DFS 함수를 실행한다.

4. 탐색 종료 시 True 반환

인접 노드까지 모두 탐색을 완료했다면 True를 반환하여 종료를 알린다.

 

 

 

만약 안전 영역과 섬의 개수 문제의 상세 풀이를 확인하고 싶다면 아래 링크를 참고하자.

 

- 안전 영역: https://developer-zoyh.tistory.com/18

[백준][DFS] 99클럽 코테 스터디 4일차 TIL + 안전 영역 (+ RecursionError 핸들링 하기)

 

- 섬의 개수: https://developer-zoyh.tistory.com/21

[백준][DFS] 99클럽 코테 스터디 6일차 TIL + 섬의 개수

 

 

 

5. 오늘의 후기

어렵다고 생각하던 DFS의 1차 관문을 넘은 기분이 든다. 이제 BFS를 시도할 용기도 난다.

다음 주 DFS, BFS 문제를 다양하게 풀어보며 완벽 정복해버려야겠다.

그리고 얼른  재귀 함수 사용하지 않는 DFS도 시도해봐야지. 히히. 화이팅!