[Python] 백준 2468번 안전영역

문제

2468번: 안전 영역

입력

• 첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

• 첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

입력 예제

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

7
9 9 9 9 9 9 9
9 2 1 2 1 2 9
9 1 8 7 8 1 9
9 2 7 9 7 2 9
9 1 8 7 8 1 9
9 2 1 2 1 2 9
9 9 9 9 9 9 9

출력 예제

5

6

문제 풀이

• 높이 값이 최대 100으로 크지 않으므로 높이 값을 0일 때 부터 100일 때 까지의 모든 경우를 탐색하여 안전영역의 개수를 비교한다.
• 물에 잠기는 좌표를 저장하기 위한 리스트를 만든 후 그래프의 값이 현재 탐색 중인 높이 값 이하이면 물에 잠기므로 값을 1로 바꾸기.
• 이후 잠긴 좌표가 저장되어있는 리스트에서 값이 0인(잠겨있지 않은 곳) 곳을 차례대로 BFS로 탐색을 진행 한 후, 탐색이 끝나면 카운트.
• 이후 카운트 값 (안전영역의 개수) 중 최대 값을 출력.

나의 코드

from collections import deque
dy = [-1,1,0,0]
dx = [0,0,-1,1]
n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))

def bfs(y,x,weat_list):
    queue = deque()
    queue.append((y,x))
    weat_list[y][x] = 1
    while queue:
        yy,xx = queue.popleft()
        for i in range(4):
            ny = yy + dy[i]
            nx = xx + dx[i]
            if 0 <= ny < n and 0 <= nx < n and weat_list[ny][nx] == 0:
                weat_list[ny][nx] = 1
                queue.append((ny,nx))

# 0 ~ 100까지 차례대로 물에 잠기게 하기
def rain():
    result = []
    for i in range(101):
        cnt = 0
        weat_list = [[0] * n for _ in range(n)]
        for j in range(n):
            for k in range(n):
                if graph[j][k] <= i:
                    weat_list[j][k] = 1

        # # 안전영역 수 구하기
        for y in range(n):
            for x in range(n):
                if weat_list[y][x] == 0:
                    cnt += 1
                    bfs(y,x,weat_list)
        result.append(cnt)
    return result

print(max(rain()))

주의할 점

• 높이 값이 변경 될 때 마다 for문 안에서 잠긴 곳을 탐색하는 weat_list를 초기화 해줘야 하는데 전역변수로 선언 한 후 계속 삽질 했다. 여러 번 탐색하는 경우라면 꼭 탐색 할 때 마다 리스트를 초기화 해주기

다른 사람 풀이

• 리스트에 각 행들의 값을 입력 받을 때 최댓값을 탐색하여 그래프 입력을 마친 후 그래프의 최댓값을 저장
• 물에 잠기는 높이가 최댓값인 경우 모든 곳이 잠기므로 안전영역의 개수가 0이기 때문에 높이 - 1인 경우까지만 탐색
• 물에 잠기지 않은 경우는 탐색하고 있는 높이보다 그래프에 있는 값이 더 큰 경우 이므로, 이 경우 잠기지 않았다고 보고 BFS 탐색을 진행한다. 이 때 현재 탐색하고 있는 높이 값을 같이 넘겨줘야 탐색을 진행할 수 있다.
• 탐색 진행시 방문처리 되지않았고, 현재 탐색하고 있는 높이보다 그래프의 값이 더 큰 경우라면 안전영역이므로 큐에넣고 계속 탐색한다.
• BFS를 마쳤다면 안전영역이 상하좌우 인접해 있는 하나의 경우를 탐색한 것이므로 카운트한다.
• 안전영역의 개수를 모두 탐색 한 후 최댓값을 저장하여 출력한다.

코드

from collections import deque

n = int(input())
max_num = 0
graph = []

for _ in range(n):
    row = list(map(int,input().split()))
    graph.append(row)

    # 그래프 내 최댓값
    for i in row:
        if i > max_num:
            max_num = i

dy = [-1,1,0,0]
dx = [0,0,-1,1]

def bfs(y,x,num):
    queue = deque()
    queue.append((y,x))
    visited[y][x] = 1

    while queue:
        y, x = queue.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < n and 0 <= nx < n:
                if graph[ny][nx] > num and not visited[ny][nx]:
                    visited[ny][nx] = 1
                    queue.append((ny, nx))


result = 0
for i in range(max_num):
    cnt = 0
    visited = [[0] * n for _ in range(n)]
    for j in range(n):
        for k in range(n):
            # 물에 잠기지 않는 경우
            if not visited[j][k] and graph[j][k] > i:
                bfs(j,k,i)
                cnt += 1
    result = max(result, cnt)

print(result)

결과

• 속도와 메모리 면에서 나의 풀이가 더 효율적이었다.
• 그러나 최대 높이 값이 100이 아닌 더 큰 값으로 늘어날 경우 아래의 풀이가 훨씬 효율적일 것이다.
• 탐색하려는 값이 작으면 브루트 포스 알고리즘 적용하여 모든 경우 탐색하기