[백준] 2583번 - 영역 구하기 (DFS / BFS)

오늘은 문제를 보자마자알 수 있는 DFS, BFS 분류의 문제를 풀어보았습니다.

오랜만에 풀어서 조금 감을 잃었는지 조금 헤매면서 풀었던 것 같네요 😅

바로 풀이 보시죠!!!

 

1. 문제

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

2583번: 영역 구하기

2. 풀이

문제 입력부터 확인하면, 첫번째 줄에 세로, 가로, K 를 입력하고 (K는 모눈종이의 직사각형의 개수)

두번째 줄부터 직사각형의 꼭짓점 좌표를 하나씩 입력받습니다.

 

문제에서 해당 직사각형을 제외한 부분의 영역을 구해야 하므로,

값을 입력 받을 때 직사각형 부분은 방문된 영역이라고 표시합니다. 

그리고 이제 전체 M X N 크기의 모눈종이의 방문 여부를 확인하면서 분리된 영역의 값을 구합니다.

방문하지 않았으면 res 배열의 값에 시작 값을 넣고 DFS 또는 BFS를 돌립니다.

돌릴 때마다 분리된 한 영역을 방문하겠죠 ?

이 때 한 영역의 넓이를 계산해줘야 하므로 cnt 값을 같이 넘겨줍니다.

DFS 풀이로는 재귀호출을 통해 영역의 값을 세고,

BFS 풀이로는 큐를 사용하여 해결해줍니다.

 

def 부분을 살펴보면, 전형적인 DFS, BFS 풀이죠?

현재 위치의 상하좌우를 비교해서 영역을 벗어나지 않고

방문한 적 없으면 방문처리를 하고 재귀 or 큐에 넣어 영역의 값을 카운팅 합니다.

 

출력은 영역의 개수와 각 영역의 넓이를 오름차순으로 정렬해줘야 하므로

첫번째 출력은 res 길이를,

두번째 출력은 *res 를 이용해서 리스트의 값을 반복문을 사용하지 않고도 바로 출력할 수 있다. (이제야 알다니!!)

 

3. 코드

* DFS 풀이

* BFS 풀이