농장 관리 ( 1245 번 )

1245번: 농장 관리

 

---

🧠 알고리즘

• BFS(너비 우선 탐색) + Flood Fill

 

✔️ 동작 방식

• 격자(N×M)를 입력받아 map_list에 저장
• 방문 여부를 visit 배열로 관리
• 각 좌표 (i, j)에서 방문하지 않은 지점을 시작점으로 BFS 실행 →  동일한 높이를 가진 연결된 영역(산)을 모두 방문 처리
• BFS 도중 인접한 8방향 탐색 시 현재 높이보다 더 높은 지형이 발견되면 → 해당 영역은 산봉우리 아님(check = False)
• BFS가 끝났을 때 check가 True라면, 해당 영역은 산봉우리 → answer += 1
• 전체 탐색 후 산봉우리 개수 출력

---

 

🧾 코드

import sys
from collections import deque

def _main(n, m):
    answer = 0
    visit = [[False] * m for _ in range(n)]
    map_list = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

    for i in range(n):
        for j in range(m):
            if visit[i][j] is False: # 미 방문 경우
                now_hg = map_list[i][j]
                visit[i][j] = True
                queue = deque([(i, j)])

                check = True
                while queue:
                    x, y = queue.popleft()

                    for n_x, n_y in ((x-1, y-1), (x, y-1), (x+1, y-1), (x+1, y), 
                                     (x+1, y+1), (x, y+1), (x-1, y+1), (x-1, y)):
                        if (0 <= n_x < n) and (0 <= n_y < m): 
                            if (map_list[n_x][n_y] == now_hg) and (visit[n_x][n_y] is False):
                                visit[n_x][n_y] = True
                                queue.append((n_x, n_y))
                            elif (map_list[n_x][n_y] > now_hg):
                                check = False

                if check:
                    answer += 1    
    
    return answer
    

n, m = map(int, sys.stdin.readline().rstrip().split())
print(_main(n, m))

---

 

⏱️ 시간 복잡도

for i in range(n) : 모든 칸은 순회하며 BFS 탐색 ( 이차형 시간 복잡도 )
	for j in range(m) :
    
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )