2468 안전 영역
import sys
sys.setrecursionlimit(10**6)
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def dfs(x, y, check_num):
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if (0<= nx < N) and (0 <= ny < N):
if heights[nx][ny] > check_num and visited[nx][ny]==0:
visited[nx][ny] = 1
dfs(nx, ny, check_num)
N = int(input())
heights = []
for _ in range(N):
heights.append(list(map(int, input().split())))
answer = 0
for check_num in range(max(map(max, heights))):
result = 0
visited = [[0]* N for _ in range(N)]
for i in range(N):
for j in range(N):
if heights[i][j] > check_num and visited[i][j] == 0:
visited[i][j] = 1
result += 1
dfs(i,j,check_num)
answer = max(answer, result)
print(answer)
내가 이해한 룰
- 인접해 있는 지역들을 하나의 안전지역으로 보았을 때
- 강수량에 따라 변하는 안전지역의 갯수의 최댓값을 구하는 문제
- 강수량은 1부터 지역높이의 최대치까지 검사해야한다.
- 안전지역이 만들어지지 않는 곳도 있다.
문제풀이 - dfs
- heights라고 명명한 2차원리스트 전체를 순회하면서
- 현재 강수량보다 값이 높고 방문하지 않은 값들을 방문처리해주고
- dfs에 담아 다시 인접한 곳들에서 강수량 보다 높은 값을 검사해 dfs 재귀함수에 담아준다.
- 4방향을 검사하고 그 값이 리스트의 범위를 초과하지 않는지 검사한다.
- 초과하지 않고 또 그 새로운 방향의 값이 강수량을 넘고 방문하지 않았다면
- 다음 방향 값을 dfs에 다시금 넣어주어 인접한 지역을 검사해준다.
- 마지막으로 최대값을 구하는 문제이므로 0으로 초기화해둔 answer과 강수량별 안전지역의 갯수가 담긴 result값을
- for문이 돌 때 마다 max로 검사해 둘 중에서 최대값을 answer에 저장해준다.
- 마지막으로 answer를 프린트해준다.
from collections import deque
def bfs(check_x, check_y, check_num):
stack = deque()
stack.append((check_x,check_y))
visited[check_x][check_y] = 1
while stack:
x, y = stack.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if heights[nx][ny] > check_num and visited[nx][ny] == 0:
visited[nx][ny] = 1
stack.append((nx, ny))
N = int(input())
heights = []
for _ in range(N):
heights.append(list(map(int, input().split())))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
answer = 0
for check_num in range(max(map(max, heights))):
result = 0
visited = [[0] * N for _ in range(N)]
for i in range(N):
for j in range(N):
if heights[i][j] > check_num and visited[i][j] == 0:
bfs(i,j, check_num)
result +=1
answer = max(answer, result)
print(answer)
문제풀이 - bfs
- 기본로직은 같으나 방문처리를 스택으로 처리해주었다.
- dfs와 같이 다음 방문할 위치에 있는 값이 강수량을 넘고 방문하지 않았다면
- 스택에 넣어주어 이동한 곳의 인접 지역을 다시 검사할 수 있도록 해준다.