[Python] 백준 1245번 문제, 농장 관리

<문제 링크>

 

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

1245번: 농장 관리

 

---

<풀이>

 

이 문제는 그래프 탐색을 통해 산봉 우리의 갯수를 출력해내는 문제이다.

해결법으로는 기본 DFS 알고리즘에서 하나의 조건문을 추가해줘야한다.

 

그 조건문은 현재 산봉우리의 주변을 탐색하면서 자신보다 큰 산봉우리가 있는지를 판단한다.

자신보다 큰 산봉우리가 있다면 Trigger를 False로 변경해 산봉우리 갯수를 세는 count를 증감하지 않고,

자신보다 큰 산봉우리가 없다면 맨 꼭대기이므로 Trigger를 True로 되어 있기 때문에 count를 증감한다.

 

자신이라고 지칭하는 산봉우리는 main에서 dfs()를 호출한 시작 산봉우리이며, 위 조건문을 수행하기 위해

자신의 주변에 자신과 같은 값을 가진 산봉우리가 있다면 그래프 탐색을 통해 나아가 다음 산봉우리에서 위에 언급한 조건문이 해당하는지를 계속 판단한다.

 

그래서 (0, 0)부터 (N-1, M-1)까지 for문을 작동시키면 산봉우리의 총 개수가 나온다.

 

---

<코드>

farm[][]: N * M 크기의 산봉우리 정보가 담긴 리스트

visited[][]: farm과 같은 크기의 방문 여부 확인을 위한 리스트

move[]: 시계 방향으로 움직이기 위한 이동 좌표값을 저장한 리스트

trigger: 지금 산봉우리가 가장 큰 산봉우리인지를 판단해주는 변수

---

import sys

def dfs(i, j):
    global trigger
    visited[i][j] = True

    for m in range(len(move)):
        x = i + move[m][0] # 주변 산봉우리 확인
        y = j + move[m][1]

        if (0 <= x < N) and (0 <= y < M):
            if farm[i][j] < farm[x][y]: # 자기보다 높은 산봉우리가 있다면
                trigger = False # farm[i][j]는 산봉우리가 아님
            if not visited[x][y] and farm[x][y] == farm[i][j]: # 같은 높이의 산봉우리 확인
                dfs(x, y)

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    farm = [[] for _ in range(N)]
    visited = [[False for _ in range(M)] for _ in range(N)]
    move = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)] # 12시부터 시계 방향
    count = 0

    # create farm
    for i in range(N):
        farm[i] = list(map(int, sys.stdin.readline().split()))

    # logic
    for i in range(N):
        for j in range(M):
            if farm[i][j] > 0 and not visited[i][j]:
                trigger = True # init
                dfs(i, j)
                if trigger: # farm[i][j]는 산봉우리임
                    count += 1

    print(count)