개발하는데 다 이유가 있겠지

알고리즘 문제풀이

2468. 안전영역

• 그래프 탐색으로 모든 좌표 순회
• 방문여부(visited)와 높이로 조건 설정
• 시간초과 발생..

from collections import deque
import sys
input = sys.stdin.readline
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
deq = deque()


def search(graph, height):
    visited = [[0]*n for i in range(n)]
    count = 0

    for y in range(n):
        for x in range(n):
            if graph[x][y] > height and visited[x][y] == 0:
                deq.append((x, y))
                count += 1
                visited[x][y] = 1

            while deq:
                x, y = deq.popleft()
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if n > nx >= 0 and n > ny >= 0 and graph[nx][ny] > height and visited[nx][ny] == 0:
                        deq.append((nx, ny))
                        visited[nx][ny] = 1

    return count


n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
arr = []
for i in range(1, 101):
    arr.append(dfs(graph, i))

print(max(arr))

---

2630.색종이

• 분할 정복으로 작은 단위로 쪼개서 재귀를 통해 해결해야 함

import sys
input = sys.stdin.readline


def solution(paper, size, x, y):
    total = 0
    if size < 2:
        if paper[x][y] == 1:
            color[1] += 1
            return
        else:
            color[0] += 1
            return

    midX = size//2
    midY = size//2
    endX = size+x
    endY = size+y
    
    for i in range(x, endX):
        for j in range(y, endY):
            total += paper[i][j]

    if total == size*size:
        color[1] += 1
        return
    elif total == 0:
        color[0] += 1
        return

    solution(paper, size//2, x, y)  # 1사분면
    solution(paper, size // 2, x+midX, y)  # 2사분면
    solution(paper, size // 2, x, y+midY)  # 3사분면
    solution(paper, size // 2, x+midX, y+midY)  # 4사분면


color = [0, 0]  # white : color[0] / blue : color[1]
paper_size = int(input())
paper = [list(map(int, input().split())) for _ in range(paper_size)]

solution(paper, paper_size, 0, 0)
print(*color,sep="\n")