-
1245. [Python]농장 관리Python_알고리즘/Gold V 2023. 10. 21. 15:35
1. 문제
https://www.acmicpc.net/problem/1245
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- BFS(너비 우선 탐색)
3. 파이썬 코드
from collections import deque from pprint import pprint # 8방향 탐색 direction = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] def BFS(start): # 봉우리 체크할 변수 global check_tree q = deque([start]) # 시작지점 방문처리 visited[start[0]][start[1]] = True while q: check = q.popleft() # 방향 탐색 for k in range(8): ny = check[0] + direction[k][0] nx = check[1] + direction[k][1] if ( 0 <= ny < N ) and ( 0 <= nx < M ): # 주위에 큰 봉우리가 있는경우 봉우리 아니라는 체크 if matrix[ny][nx] > matrix[check[0]][check[1]]: check_tree = False # 방문하지 않았고 값이 같은 봉우리가 있으면 방문처리 후 q에 추가 if not visited[ny][nx] and matrix[ny][nx] == matrix[check[0]][check[1]]: visited[ny][nx] = True q.append((ny,nx)) N, M = map(int,input().split()) matrix = [ list(map(int,input().split())) for _ in range(N) ] visited = [ [0] * M for _ in range(N) ] cnt = 0 for i in range(N): for j in range(M): # 방문하지 않으면 함수 실행 if not visited[i][j]: # 초기값 봉우리 True 선언 check_tree = True BFS((i,j)) # 만약 봉우리가 true 라면 cnt 증가 if check_tree: cnt += 1 print(cnt)
4. 문제를 풀고난 후 생각
- 주변의 봉우리가 있는지 없는지 체크를 해가며 탐색을 진행하는 문제고, 봉우리인지 아닌지 판단해주는 변수 선언을 통해서 봉우리가 있는경우 cnt 값을 증가시켜 봉우리 갯수를 세어준다.
- 한 값을 기준으로 탐색을 진행해서 그 값과 같은 봉우리가 있으면 q에 추가해서 좌표를 옮긴 후 방향배열 탐색을 진행하며 그 값이 봉우리인지 체크해준다.
- 이렇게 모든 좌표를 탐색한 후 cnt 값을 출력해주면 봉우리가 몇개가 존재하는지 알 수 있다.
5. 문제를 푸는데 도움이 되는 지식
- BFS(너비 우선 탐색)
'Python_알고리즘 > Gold V' 카테고리의 다른 글
1490. [Python]자리수로 나누기 (0) 2023.11.01 1374. [Python]강의실 (0) 2023.10.30 7490. [Python]0 만들기 (0) 2023.10.11 1759. [Python]암호 만들기 (0) 2023.10.09 1107. [Python]리모컨 (1) 2023.10.02