[백준] 1245번 농장 관리

💡문제접근

• 산봉우리의 정의를 다시 한 번 되짚어보자.
• 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다.
• 위의 산봉우리의 정의를 정리해보면 인접한 방향은 상하좌우 그리고 대각선 방향도 포함된다.
• 뿐만 아니라 높이가 0인 산봉우리는 산봉우리로 취급하지 않고 만약 인접한 좌표의 높이가 현재 좌표의 높이와 같은 경우라면 재귀를 사용해서 인접한 방향으로 계속 나아가면서 산봉우리의 끝을 찾는 방식으로 코드를 작성했다.
• 공부하는 차원에서 DFS, BFS 탐색 알고리즘을 모두 사용해서 문제를 풀어봤다.

💡코드1(메모리 : 31256KB, 시간 : 64ms) - DFS

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, M = map(int, input().strip().split())
farm = [list(map(int, input().strip().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]

def DFS(a, b):
    global flag
    da = [0, 1, 1, 1, 0, -1, -1, -1]
    db = [-1, -1, 0, 1, 1, 1, 0, -1]
    for i in range(8):
        na = a + da[i]
        nb = b + db[i]
        if na < 0 or na >= N or nb < 0 or nb >= M:
            continue
        if farm[na][nb] > farm[a][b]:
            flag = False
        if 0 <= na < N and 0 <= nb < M and not visited[na][nb] and farm[na][nb] == farm[a][b]:
            visited[na][nb] = True
            DFS(na, nb)

cnt = 0
for i in range(N):
    for j in range(M):
        if farm[i][j] > 0 and not visited[i][j]:
            flag = True
            DFS(i, j)

            if flag:
                cnt += 1
print(cnt)

💡코드2(메모리 : 34192KB, 시간 : 84ms) -BFS

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
farm = [list(map(int, input().strip().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]

def BFS(a, b):
    global flag
    queue = deque()
    queue.append((a, b))
    visited[a][b] = True
    while queue:
        x, y = queue.popleft()
        dx = [0, 1, 1, 1, 0, -1, -1, -1]
        dy = [-1, -1, 0, 1, 1, 1, 0, -1]
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if farm[nx][ny] > farm[x][y]:
                flag = False
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and farm[nx][ny] == farm[x][y]:
                visited[nx][ny] = True
                queue.append((nx, ny))

cnt = 0
for i in range(N):
    for j in range(M):
        if farm[i][j] > 0 and not visited[i][j]:
            flag = True
            BFS(i, j)
            if flag:
                cnt += 1
print(cnt)

💡소요시간 : 10m