ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [알고리즘] 백준 1245 농장 관리
    알고리즘 2022. 8. 6. 16:52
    728x90

    문제

    농장 관리

    접근

    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)
Designed by Tistory.