백준, 안전영역 (Python)

 

문제

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

2468번: 안전 영역

 

해당 문제는 모든 노드를 방문해서 확인해야하는 문제로, 전형적인 경로 탐색의 문제로 보입니다.

 

이럴경우 대표적으로 BFS, DFS를 사용합니다.

BFS, DFS는 대표적인 그래프 탐색 알고리즘이며, 탐색 우선순위가 깊이인지 너비인지의 차이가 있습니다.

BFS는 현재 위치를 기준으로 가장 가까운 노드를 순차적으로 방문하는 너비 탐색 알고리즘이고,

DFS는 탐색 방향을 기준으로 해당 방향의 노드를 방문하는 깊이 탐색 알고리즘입니다. 

 

BFS를 사용한 이유

 

해당 문제의 경우 물에 잠기지 않은 안전영역을 체크하는데, 안전 영역은 물에 잠기지 않은 지점들이 인접해있는 최대 영역을 말합니다.

따라서 현재 위치를 기준으로 가장 가까운 지점이 안전한 곳인지 탐색을 해야하기 때문에 BFS를 사용하였습니다.

 

 

문제풀이

import sys

def solved(n, arr, search):
    answer = []
    for snum in search:
        cnt = 0
        checked = [[0]* n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if arr[i][j] > snum and checked[i][j] == 0:
                    checked[i][j] = 1
                    BFS(n, arr, snum, checked, [(i,j)])
                    cnt += 1
                else:
                    continue
        answer.append(cnt)
    return max(answer)

def BFS(n, arr, k, checked, queue):
    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]
    while queue:
        x, y = queue.pop(0)
        for idx in range(4):
            nx = dx[idx]+x
            ny = dy[idx]+y
            if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] > k and checked[nx][ny] == 0:
                checked[nx][ny] = 1
                queue.append((nx,ny))

if __name__ == "__main__":
    for i in range(1, 5 + 1):
        sys.stdin = open(f"in{i}.txt", "r")
        num = set()
        arr = []
        n = int(input())
        for _ in range(n):
            a = list(map(int, input().split()))
            arr.append(a)
            for hh in a:
                num.add(hh)
        print(solved(n, arr, num) == int(open(f"out{i}.txt", "r").read()))

 

 

1) 초기 값 설정 - 탐색 제한 search 설정

해당 영역의 값은 1부터 100까지 사이로 지정되어있지만, 

관련 값을 넣는 arr를 생성하면서, 실제 값을 set 으로 받아 중복을 제거하여 실제 값이 들어가있는 수들을 넣은 set 데이터 구조를 사용하여, 100보다 더 적은 탐색을 할 수 있도록 만들었습니다.

문제의 값이 이럴경우, 1~100까지 도는것보다 search 값에는 {2,3,4,5,6,7,8,9} 의 값이 저장되어

총 8번만 돌 수 있게 탐색 수를 줄여 성능을 높이고자 하였습니다.

 

2. checked 함수 사용

checked 함수를 사용해 중복된 값이 queue 에 들어가지 않도록 하여, 중복 탐색을 방지하여 성능을 높혔습니다.

 

3. BFS 구현

모든 곳을 탐색하면서, search 의 수보다 더 높은 수의 안전영역을 만나면, 그 값을 queue 에 넣어 상하좌우의 인접 영역을 탐색하게 만들었습니다. 해당 인접영역을 방문하면 checked함수에 1을 넣어 해당 탐색 경로를 방문했다는 기록을 남겨 더이상 중복적으로 queue 에 값이 들어가지 않게 방지하였습니다.

 

4. cnt

BFS 함수가 끝나면 cnt 함수에 숫자를 증가시켜 몇개의 안전영역이 있는지 체크하였고, 안전영역 갯수를 anwer list 에 append 하는 형식으로 구현하였습니다. 이후 search 에있는 값을 모두 탐색헀을때 안전영역의 최대갯수가 answer 변수에 저장이 되고, 그 중 최댓값을 return 하여 최대 안전 영역이 몇인지 반환하여 문제를 풀었습니다.

 

시간복잡도

해당문제의 시간복잡도는 BFS 시간복잡도인 O(N^2)입니다.