[백준][DFS] 섬의 개수

오늘의 학습 키워드

DFS

 

오늘의 회고

🌱 오늘의 문제

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

배열의 크기(w, h)와 배열이 여러 번 반복하여 주어질 때, 그 배열에 포함된 섬의 개수를 세는 문제이다.

 

[주의할 점]

1. 테스트 케이스의 개수가 고정되어 있지 않아 시간 복잡도를 예측하기 어려움

이 문제에서는 w, h의 입력이 0 0으로 주어질 때 프로그램을 종료한다. 너비와 높이인 w와 h가 50 이하의 정수이므로, 배열의 크기가 많이 크지는 않으나 테스트 케이스가 몇 개나 반복될 지 모른다는 점에서 시간 복잡도를 예측하기 어렵다.

2. 상하좌우 + 대각선 이동 가능

상하좌우 뿐만 아니라 대각선으로도 이동 가능하다. 출발점 기준으로 인접한 8개의 위치를 모두 고려해주어야 한다.

 

 

우선 간단하게 DFS를 이용하여 풀어보았다.

 

 

🌱 나의 시도

1. "0 0"이 입력으로 주어질 때까지 전체 과정을 반복하므로 While 문을 사용한다.

2. 너비, 높이 값을 입력으로 받고 While문의 정지 조건을 걸어준다.

3. 높이*너비 크기의 지도 배열(user_map)과 방문 여부를 저장할 배열(visited)을 정의한다.

4. 입력 받은 지도 값을 기준으로 Land(1)만 이동 가능하므로, Sea(0)는 visited 배열에 True로 저장하여 이미 방문한 것으로 처리한다.

* 1. 방문을 막기 위한 목적 / 2. 코드에서 Sea 인지 판단하는 조건문을 제거하여 코드를 간소화 하기 위함

5. 반복문을 돌며 방문하지 않은 위치에 대해 DFS 함수를 수행한다. -> O(n^2)

 

6. 배열 내에 위치한 인접 Land에 대해 DFS를 재귀적으로 호출하여 영역의 전체 구간을 살핀다.

7. 처음 호출한 구간을 기준으로 전체 영역의 호출을 마치면 True를 반환한다.

 

8. DFS에서 True가 반환된 개수만큼 answer에 1을 증가시켜 개수를 더해준다.

9. 최종적으로 구한 답을 출력한다.

 

 

-> 내가 생각한 본 문제의 시간 복잡도는 O(n^2)이다.

2차원 배열을 순회하며 DFS 함수를 실행하는 것이 가장 많은 시간을 소모하는 것으로 판단된다.

이 부분에서 방문한 노드는 다시 방문하지 않으므로 재귀적으로 호출하더라도 2차원 배열을 전체 한 번 순회하는 것과 비슷한 수준이라고 생각되어 O(n^2)이라고 생각하였다.

 

위 내용을 코드로 작성하면 아래와 같다.

def dfs(x, y, visited, w, h):
    dirs = [[-1, -1], [-1, 0], [-1, 1],
            [0, -1], [0, 1],
            [1, -1], [1, 0], [1, 1]]
    
    visited[x][y] = True
    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)

 

 

🌱 새롭게 알게 된 점

대각선 방향이 추가되어도 DFS에서 이동하는 방향 배열만 조정해주면 쉽게 풀 수 있었다.

지난 번에 풀어본 문제는 상하좌우만 고려했기 때문에 처음 문제를 읽을 때에는 대각선을 고려해야 한다는 부분이 조금 부담스러웠다.

그런데 별 거 아니라는 것을 알고 나니 다른 문제를 풀 때에도 지레 겁 먹지 않아도 된다는 생각이 들었다.

 

 

오늘의 후기

지난 번 안전 영역 이후로 DFS를 통해 영역의 개수를 구하는 문제의 원리를 확실히 이해하게 되었다.

방문하지 않은 어떤 Land(1) 값을 기준으로 최대 깊이까지 모두 탐색을 마치고 나면, 처음 시작한 지점 기준으로 인접한 최대 넓이의 영역을 하나 구할 수 있다.

이 원리에 대해서 완벽히 이해할 수 있어서 참 좋았다.