[백준/2583/파이썬] 영역 구하기

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

2583번: 영역 구하기

이 문제의 핵심은 DFS/BFS이다.

하지만,  난 그것보단, 좌표 -> 배열로 나타내는 과정이 상당히 인상깊었다.

이 문제는, 사각형의 범위를 시작점 (x1,y1) , 끝나는점(x2,y2)로 나타내었음.

아래와 같이, 빨간영역의 직사각형이라면, 0 1 2 2 로 입력을 한다는 소리임!

컴퓨터의 배열은 0부터 시작하고, 행렬의 개념으로, 좌표의 개념과 다르다.

 

하지만, 직사각형의 영역을 배열에 나타내기 위해서, 반복문을 어떻게 쓸까 생각해보면, 이렇게 할 수 있다.

시작점 (x1,y1) , 끝나는점 (x2,y2)라고 할 때, 입력은 그럼, x1,y1,x2,y2로 들어오게되고, 아래와 같이 반복문을 사용하면, 직사각형의 영역을 손쉽게 나타낼 수 있음.

for a in range(y1,y2):
	for b in range(x1,x2):
    	board[a][b] =1

 

 

코드는 이번에는 DFS를 이용해봤다.

import sys
sys.setrecursionlimit(10**6)
N,M,K = map(int,input().split())
board = [[0]*M for _ in range(N)]
v_chk = [[False]*M for _ in range(N)]
area=[]
dx=(0,1,0,-1)
dy=(1,0,-1,0)
for i in range(K):
    x1,y1,x2,y2=map(int,input().split())
    for a in range(y1,y2):
        for b in range(x1,x2):
            if board[a][b] ==0:
                board[a][b] =1
"""
for b in board:
    print(b)
"""
cnt=0
def dfs(y,x):
    global cnt
    v_chk[y][x]=True
    cnt+=1
    for k in range(4):
        ny=y+dy[k]
        nx=x+dx[k]
        if (0<=ny<N and 0<=nx<M) and board[ny][nx] ==0 and not v_chk[ny][nx]:
            dfs(ny,nx)

for i in range(N):
    for j in range(M):
        if board[i][j] ==0 and not v_chk[i][j]:
            cnt=0
            dfs(i,j)
            area.append(cnt)

area = sorted(area)
print(len(area))
for a in area:
    print(a,end=" ")