[백준 파이썬] 1245 농장 관리

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

1245번: 농장 관리

 

 

문제

농장의 높이가 주어지고 산봉우리의 개수를 구하는 문제이다.

 

---

 

풀이

농장에 높이가 주어지므로 산봉오리를 구하는 식을세우면 된다.

산봉오리는 인접 8개의 방향보다 높은 곳이므로 dfs를 이용하여 해결하였다.

 

def dfs(r, c):
  nowHeight = farm[r][c]
  stack = [(r, c)]
  flag = True

  while stack:
    r, c = stack.pop()
    for dr, dc in drc:
      nr = r + dr
      nc = c + dc
      if 0 <= nr < N and 0 <= nc < M:
        if not visited[nr][nc] and farm[nr][nc] == nowHeight: #방문하지 않았고, 이동한 위치가 현재 높이와 같은경우
          stack.append((nr, nc))
          visited[nr][nc] = True
        
        elif farm[nr][nc] > nowHeight: #이동한 위치가 현재 위치보다 높을경우
          flag = False
    
  if flag:
    return True
  
  return False

 

코드를 보면 방향을 이동해준 후 방문여부를 체크하고,  두가지의 경우를 세운다

1. 이동한 위치가 이전 위치와 높이가 같은경우

    해당 경우에는 묶어서 산봉우리가 될 가능성이 있으므로 스택에 넣어준다.

 

2. 이동한 위치가 현재 위치보다 높은경우

    해당 경우는 이동한 위치가 산봉우리이므로 false를 반환한다.

 

for r in range(N):
    for c in range(M):
        if not visited[r][c] and dfs(r, c):
            cnt += 1

이렇게 모든 위치에 대해 탐색을 진행하여 false경우를 카운팅하면 해당 카운트가 산봉우리의 개수가 된다.

 

 

---

코드

N, M = map(int, input().split())

farm = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]
drc = [(0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)]
cnt = 0
stack = []


def dfs(r, c):
  nowHeight = farm[r][c]
  stack = [(r, c)]
  flag = True

  while stack:
    r, c = stack.pop()
    for dr, dc in drc:
      nr = r + dr
      nc = c + dc
      if 0 <= nr < N and 0 <= nc < M:
        if not visited[nr][nc] and farm[nr][nc] == nowHeight: #방문하지 않았고, 이동한 위치가 현재 높이와 같은경우
          stack.append((nr, nc))
          visited[nr][nc] = True
        
        elif farm[nr][nc] > nowHeight: #이동한 위치가 현재 위치보다 높을경우
          flag = False
    
  if flag:
    return True
  
  return False


for r in range(N):
    for c in range(M):
        if not visited[r][c] and dfs(r, c):
            cnt += 1

print(cnt)