주말 공부

코변·2022년 7월 2일
0

혼자 공부해보기

목록 보기
2/2

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. 인접해 있는 지역들을 하나의 안전지역으로 보았을 때
  2. 강수량에 따라 변하는 안전지역의 갯수의 최댓값을 구하는 문제
  3. 강수량은 1부터 지역높이의 최대치까지 검사해야한다.
  4. 안전지역이 만들어지지 않는 곳도 있다.

문제풀이 - dfs

  1. heights라고 명명한 2차원리스트 전체를 순회하면서
  2. 현재 강수량보다 값이 높고 방문하지 않은 값들을 방문처리해주고
  3. dfs에 담아 다시 인접한 곳들에서 강수량 보다 높은 값을 검사해 dfs 재귀함수에 담아준다.
  4. 4방향을 검사하고 그 값이 리스트의 범위를 초과하지 않는지 검사한다.
  5. 초과하지 않고 또 그 새로운 방향의 값이 강수량을 넘고 방문하지 않았다면
  6. 다음 방향 값을 dfs에 다시금 넣어주어 인접한 지역을 검사해준다.
  7. 마지막으로 최대값을 구하는 문제이므로 0으로 초기화해둔 answer과 강수량별 안전지역의 갯수가 담긴 result값을
  8. for문이 돌 때 마다 max로 검사해 둘 중에서 최대값을 answer에 저장해준다.
  9. 마지막으로 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

  1. 기본로직은 같으나 방문처리를 스택으로 처리해주었다.
  2. dfs와 같이 다음 방문할 위치에 있는 값이 강수량을 넘고 방문하지 않았다면
  3. 스택에 넣어주어 이동한 곳의 인접 지역을 다시 검사할 수 있도록 해준다.
profile
내 것인 줄 알았으나 받은 모든 것이 선물이었다.

0개의 댓글