[Python] 안전지대 - dfs, bfs로 풀기

출처 : 코드트리

 

문제 :

첫 번째 줄에는 N과 M이 공백을 사이에 두고 주어지고,

두 번째 줄부터는 N개의 줄에 걸쳐 각 행에 위치한 M개의 마을의 높이 정보가 공백을 사이에 두고 주어집니다.

k이하의 집들은 모두 물에 잠긴다고 한다. 물에 잠기지 않은 덩어리(?)들을 안전지대라고 한다면, 안전지대가 최대로 될 때의 k를 구하여라.

(집의 높이는 최대100, 따라서 빗물높이 k를 1부터 100까지 올리면서 구해야 한)

K 가 4일때 안전지대가 4로 최대인 모습

출력 : 

1 이상의 K 중, 안전 영역의 수가 최대가 될때의 K와 그 때의 안전 영역의 수를 공백을 사이에 두고 출력합니다. 만약 안전 영역의 수가 최대가 되는 K가 여러 개라면, 그 중 가장 작은 K를 출력합니다.

import sys
from collections import deque
sys.setrecursionlimit(2500)
n,m = map(int, sys.stdin.readline().split())

graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]

def in_range(x, y):
    return 0<=x and x<n and 0<=y and y<m 

# k이하 숫자들에만 dfs 탐색 진행
def less_than_k(x,y,k):
    global K
    # 범위를 벗어남
    if not in_range(x,y) : 
        return False

    # 방문했거나 잠긴 집
    if graph[x][y] <= k or visited[x][y]==True : 
        return False

    return True

dx = [1,0,-1,0]
dy = [0,-1,0,1]
cnt = 0 
visited = [ [False]*m for _ in range(n) ]
def dfs(row, col, K):
    global cnt
    for i in range(4):
        new_row = row + dx[i]; new_col = col + dy[i]
        if in_range(new_row, new_col) == False : continue
        if less_than_k(new_row, new_col, K) == True :
            visited[new_row][new_col] = True
            dfs(new_row, new_col, K)


def bfs(x, y, K):
    global cnt
    q = deque()
    visited[x][y] = True
    q.append((x, y))
    while(q) :
        pop_x , pop_y = q.popleft()
        for i in range(4):
            new_row = pop_x + dx[i]; new_col = pop_y + dy[i]
            if in_range(new_row, new_col) == False : continue
            if less_than_k(new_row, new_col, K) == True :
                visited[new_row][new_col] = True
                q.append((new_row, new_col))


k_list = [0] * (101)
#모든지점에서 bfs 탐색 진행
# 잠긴곳은 False, 안잠긴 곳은 True
for KK in range(1, 101):
    visited = [ [False]*m for _ in range(n) ]
    cnt = 0

    for i in range(n):
        for j in range(m):
            if less_than_k(i,j,KK):
                visited[i][j] = True
                cnt+=1 # dfs하기 전에 cnt up
				
                #(1) bfs 방법 - 너비우선탐색
                bfs(i, j, KK)
                # (2) dfs 방법 - 깊이우선탐색
                # dfs(i,j,KK)

    k_list[KK] = cnt

visited[0][0] = True
ans = k_list.index(max(k_list))
if ans == 0 : ans = 1
print(ans, max(k_list))