[백준]2468. 안전영역 - python

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

2468번: 안전 영역

문제풀이

• BFS 탐색 문제

• 날짜에 따라서 잠긴부분과 아닌 부분을 0과 1로 나타냄
• 그 다음, 1 인 부분(잠기지 않은 부분) 을 bfs 탐색으로 찾아내어 카운팅함
• 각 날짜별로 계산해서 그 중 최대 영역 개수를 찾아냄

코드 (python)

dir=[[-1,0],[0,1],[1,0],[0,-1]]
def bfs(start):
    que = []
    que.append(start)
    map_b[start[0]][start[1]] = 0
    while que:
        cur = que.pop(0)
        for k in range(4):
            nr = cur[0] + dir[k][0]
            nc = cur[1] + dir[k][1]
            if nr <0 or nr >= N or nc < 0 or nc >=N:continue
            if map_b[nr][nc]==0: continue
            que.append([nr,nc])
            map_b[nr][nc] = 0


N = int(input())
Map = [list(map(int,input().split())) for _ in range(N)]
maxT = 0
ans = 0
#가장 높은 지대 찾기
for i in range(N):
    for j in range(N):
        maxT = max(maxT,Map[i][j])
if maxT==1: #최대 영역이 1이라면 전체가 한덩이이므로 답은 1
    ans =1
else:
    for day in range(maxT+1):
        map_b = [[0]*N for _ in range(N)]
        for i in range(N):
            for j in range(N):
                map_b[i][j] = 1 if Map[i][j] >= day else 0  #잠긴부분 :0 /잠기지 않은 부분 :1 로 나눔
        # for row in map_b:
        #     print(row)

        cnt = 0 #안전영역 갯수
        for i in range(N):
            for j in range(N):
                if map_b[i][j] ==1:
                    bfs([i,j])  #bfs로 탐색한 횟수를 알아내서 영역 개수 탐색
                    cnt+=1
        ans = max(ans,cnt)
print('{}'.format(ans))