99클럽 코테 스터디 35일차 TIL + 백준 깊이너비탐색(실버1)

 

- 주제 : 깊이 너비 탐색

- 링크 https://www.acmicpc.net/problem/2583

-

import sys
sys.setrecursionlimit(10000)  # 재귀 깊이 제한을 10000으로 설정하여 깊은 재귀 호출을 허용한다

def dfs(x, y):
    global area_count
    area_count += 1  # 현재 영역의 크기를 1 증가하기
    graph[x][y] = 1  # 현재 위치를 방문 처리함. (1로 변경하여 다시 방문하지 않도록)
    
    # 상, 하, 좌, 우로 이동하는 좌표 변환을 위한 리스트
    dx = [-1, 1, 0, 0]  # x 좌표의 변화: 상(-1), 하(+1)
    dy = [0, 0, -1, 1]  # y 좌표의 변화: 좌(-1), 우(+1)
    
    for i in range(4):  # 상, 하, 좌, 우의 4가지 방향에 대해
        nx = x + dx[i]  # 새로운 x 좌표
        ny = y + dy[i]  # 새로운 y 좌표
        
        # 좌표가 유효하고, 아직 방문하지 않은 영역이면 DFS 수행
        if 0 <= nx < M and 0 <= ny < N and graph[nx][ny] == 0:
            dfs(nx, ny)  # 재귀적으로 DFS 호출

# 입력 처리
M, N, K = map(int, input().split())  # M: 세로 크기, N: 가로 크기, K: 직사각형의 수
graph = [[0] * N for _ in range(M)]  # M x N 크기의 2차원 리스트 초기화 (모두 0으로 채움)

# 직사각형 채우기
for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())  # 직사각형의 좌표 입력 받기
    for i in range(y1, y2):  # y1부터 y2-1까지 세로 범위
        for j in range(x1, x2):  # x1부터 x2-1까지 가로 범위
            graph[i][j] = 1  # 직사각형이 차지하는 영역을 1로 채움

# 영역의 넓이 리스트
areas = []

# 모든 영역을 탐색
for i in range(M):  # 각 행에 대해
    for j in range(N):  # 각 열에 대해
        if graph[i][j] == 0:  # 아직 방문하지 않은 영역(0)이라면
            area_count = 0  # 새로운 영역의 크기 초기화
            dfs(i, j)  # DFS를 통해 연결된 모든 영역 탐색
            areas.append(area_count)  # 탐색된 영역의 크기를 리스트에 추가

# 영역의 넓이를 오름차순으로 정렬하고 출력
areas.sort()  # 영역 크기 리스트를 오름차순으로 정렬
print(len(areas))  # 영역의 개수 출력
print(" ".join(map(str, areas)))  # 각 영역의 크기를 공백으로 구분하여 출력

 

저는 조빱인데 왜 자꾸 이런문제가 나오죠...

비기너랑 미들러랑 착각하셨나요

출제자님 ㅜㅜ...

 

우선 오늘의 배운점은 주석으로 대체