[백준][Python] 1245 농장 관리

그래프, bfs / 골드 5

⛰️

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

1245번: 농장 관리

 

 

내 풀이

from collections import deque

def bfs(x, y):
    peak = []
    q = deque()
    q.append((x,y))
    peak.append([x,y])
    current = arr[x][y] # 현재 좌표의 높이

    while q:
        cx, cy = q.popleft()

        for k in range(8):
            nx, ny = cx + dx[k], cy + dy[k]

            if 0 <= nx < N and 0 <= ny < M and [nx, ny] not in peak: # 범위 내
                if arr[nx][ny] > current: # 현재 높이보다 높은 경우 (현재 좌표가 산봉우리가 X)
                    return 0
                elif arr[nx][ny] == current: # 현재 높이와 동일 (인접한 격자를 더 검사해서 산봉우리가 맞는지 아닌지 확인해 볼 필요 O)
                    q.append((nx, ny))
                    peak.append([nx,ny])

    for k in range(len(peak)):
        arr[peak[k][0]][peak[k][1]] = 501

    return 1 
                

N, M = map(int, input().split())
arr = [[] * M for _ in range(N)]
ans = 0
dx = [-1, 1, 0, 0, 1, 1, -1, -1]
dy = [0, 0, -1, 1, 1, -1, 1, -1]
visited = [[False] * M for _ in range(N)]

for i in range(N):
    arr[i] = list(map(int, input().split()))

for i in range(N):
    for j in range(M):
        if arr[i][j] != 501:
            ans += bfs(i, j)

print(ans)

bfs(너비 우선 탐색)으로 풀었다.

 

 

코드 설명

 

인접하다 = X 좌표 차이와 Y 좌표 차이가 모두 1 이하인 경우

라고 문제에 명시되어 있으므로

현재 좌표의 상하좌우와 대각선을 검사해야 한다.

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

 

배열 전체를 검사한다.

이때, 이미 처리된 산봉우리가 아닌 경우(!= 501)에 bfs를 호출한다.

for i in range(N):
    for j in range(M):
        if arr[i][j] != 501:
            ans += bfs(i, j)

 

 

✔️ bfs 함수 내

 

peak: 산봉우리들의 좌표를 저장할 리스트

current: 현재 좌표의 높이

peak = []
q = deque()
q.append((x,y))
peak.append([x,y])
current = arr[x][y] # 현재 좌표의 높이

 

새 좌표가 범위 내에 있으면서 peak 배열에 없는 경우(방문한 적이 없는 경우),

1. 현재 높이(current) 보다 높은 땅이라면, 현재 좌표는 산봉우리가 될 수 없다. 바로 0을 리턴한다.

2. 현재 높이(current)와 같은 높이의 땅이라면, 새 좌표의 인접한 격자까지 검사해서 산봉우리가 될 수 있는지 아닌지를 확인해 볼 필요가 있다. q와 peak에 새 좌표를 추가한다.

while q:
    cx, cy = q.popleft()

    for k in range(8):
        nx, ny = cx + dx[k], cy + dy[k]

        if 0 <= nx < N and 0 <= ny < M and [nx, ny] not in peak: # 범위 내
            if arr[nx][ny] > current: # 현재 높이보다 높은 경우 (현재 좌표가 산봉우리가 X)
                return 0
            elif arr[nx][ny] == current: # 현재 높이와 동일 (인접한 격자를 더 검사해서 산봉우리가 맞는지 아닌지 확인해 볼 필요 O)
                q.append((nx, ny))
                peak.append([nx,ny])

 

while문에서 return 되지 않았다면, 현재 좌표가 산봉우리인 경우이다.

산봉우리들의 모든 좌표 값을 501로 변경하고, 1을 리턴한다.

for k in range(len(peak)):
    arr[peak[k][0]][peak[k][1]] = 501

return 1

 

 

 

🙀 어려웠던 점

 

산봉우리의 좌표 값들을 바꿔주지 않으니, 중복 카운트가 되었다.

처음에는 방문한 모든 좌표의 값을 변경하였는데, 이렇게 하면 다른 좌표를 검사할 때 옳지 않은 결과가 도출되었다.

 

 

✌🏻 해결 방법

 

bfs 함수 내에서 peak 리스트를 통해 산봉우리가 될 가능성이 있는 좌표를 항상 저장하고,해당 리스트는 산봉우리로 확정된 경우에만 좌표들 값을 변경하기 위해 사용하였다.

 

값을 변경할 때는 격자의 최대 높이인 500보다 큰 501을 사용하였다.

 

501이 아닌 경우에만 bfs 함수를 호출하기 때문에,이미 산봉우리 처리가 된 좌표는 검사하지 않는다.따라서, 중복 카운트가 발생하지 않는다.