[알고리즘] 백준 1245 농장 관리

문제

농장 관리

접근

1. bfs로 문제를 풀어보는데 기본으로 제시되는 예시도 다 맞고 다른 예시들도 맞는데 제출만 하면 안된다

2. dfs 로 접근을 해보았다

3. 인접하기에 대각선으로 갈 수 있으므로 dx, dy의 방향은 8가지

4. 'nx ny 는 현재 x y를 기준으로 주변 산봉우리 그래서 nxny가 더 크면 산봉우리의 조건에 맞지 않다' 의 조건을 통해 인접 봉우리와 높이 비교한다

5. 방문하지 않은 봉우리들을 체크하여 관리인의 총 명수를 구한다

 

풀이

# 농장관리
n, m = map(int, input().split())

board = []
for i in range(n):
    board.append(list(map(int, input().split())))

visited = [[False]*(m+1) for _ in range(n+1)]

dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]


def dfs(x, y):
    global mountainHeight

    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]

        # 주의점 : nx ny 는 현재 x y를 기준으로 주변 산봉우리 그래서 nxny가 더 크면 산봉우리의 조건에 맞지 않다
        if 0 <= nx < n and 0 <= ny < m:
            if board[x][y] < board[nx][ny]:
                mountainHeight = False
            if visited[nx][ny] == False and board[x][y] == board[nx][ny]:
                visited[nx][ny] = True
                dfs(nx, ny)


res = 0
for i in range(n):
    for j in range(m):
        if board[i][j] > 0 and not visited[i][j]:
            mountainHeight = True
            dfs(i, j)
            if mountainHeight:
                res += 1
print(res)