다시푸는 코딩 테스트 준비 일지
응시 사이트 : BOJ
문제 : 2583.영역 구하기
사용언어 : C#
난이도 : 중
풀이시간 : 미측정
유형 : DFS, BFS, 그래프 이론
문제
눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.
예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.
<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.
M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.
출력
첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.
예제 입력 1 복사
5 7 3
0 2 4 4
1 1 2 5
4 0 6 2예제 출력 1 복사
3
1 7 13문제 풀이 접근
일단 이 문제의 출처를 보고 놀랐다. 고등부 정보 레벨에서 푸는 것이라..
전체 레벨을 모르다보니 쉬운지 어려운지도 감이 안잡혔지만, 이제서야 푸는 내입장에서는 이 문제를 푼 고등부 친구들이 대단해보였다.
문제로 다시 돌아가서, 이 문제는 이전의 BFS, DFS 문제들과의 차이점이 조금 있었다.
차이점이라고 한다면, 이전 문제들은 각 좌표의 값은 0,1 등 정수로 다 채워서 주긴했었는데, 이 문제는 내가 그 좌표의 값을 채워야했다.
n,m 같은 사이즈만 주고 좌표를 줘서 알아서 색칠하는것이 추가된 문제다.
그리고 나서는, 한번 BFS를 돌았을때 갈 수 있는 영역을 카운팅해서 출력하면된다.
이 BFS 돈 뒤에 영역 카운팅 하는건 내가 풀었던 문제중 2667.단지번호붙이기 라는 좋은 문제가 있다.
이 문제를 아직 안풀었다면, 먼저 풀고오면 도움이 될 것이다.
플로우를 짠다면 이렇게 된다.
1. n,m 을 입력 받은 후 visited 를 구성한다. 여기선 맵은 필요없다 그냥 visited 배열로 하면된다.
2. 직사각형 좌표를 줄 것이고, 이 직사각형 각각의 좌표는 좌하 0,0 우상 max,max다
3. 좌표를 넘겨받아 좌하부터 우상까지 순회하며 그 공간을 visited[현재x값,현재y값]을 칠해준다.
4. 시작점을 찾기위해 n,m 값을 순회하면서 visited값이 false 일 경우 BFS 시작점으로 잡고 순회한다.
5. 시작점마다 순회할 수 있는 칸을 list에 넣고, 영역의 총 갯수와, 영역 사이즈를 오름차순으로 출력한다.
문제에서는 전체 좌하를 (0,0)으로 풀었으나, 나는 좌상을 (0,0)으로 아래로 갈 수록 y+ 이 되는 것으로 가정하고 풀었다.
그렇다보니, 2번의 영역이 위아래가 반전된 형식이다.
가정하기에 따라 상하또는 상관 없으므로 이렇게 진행해도 된다.
내 풀이식에서 혹시나 나중에 내가 읽었을때 의문점이 발생할 수 있기 때문에 미리 설명을 남겨 놓는다.
정답 작성 코드 (C#)
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.InteropServices;
using System.Security.AccessControl;
using System.Security.Authentication;
using System.Security.Cryptography;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Web;
using System.Xml.Linq;
using static CodingTestProj.Program;
/*
* Difficulty : Middle
* URL : https://www.acmicpc.net/problem/2583
*/
namespace CodingTestProj
{
internal class Program
{
static void Main(string[] args)
{
//Case 0 _ Short
Solution solution = new Solution();
solution.solve();
}
}
public class ColoringPos
{
public ColoringPos(int startX, int startY, int endX, int endY)
{
this.coloringStartPosX = startX;
this.coloringStartPosY = startY;
this.coloringEndPosX = endX;
this.coloringEndPosY = endY;
}
public int coloringStartPosX;
public int coloringStartPosY;
public int coloringEndPosX;
public int coloringEndPosY;
}
public class Solution
{
int n;
int m;
int k;
bool[,] visited;
int[] dx = new int[4] { 0, 0, -1, 1 };
int[] dy = new int[4] { 1, -1, 0, 0 };
List<ColoringPos> list = new List<ColoringPos>();
List<int> sectorList = new List<int>();
public void solve()
{
string[] inputs = Console.ReadLine().Split(' ');
n = Int32.Parse(inputs[0]);
m = Int32.Parse(inputs[1]);
k = Int32.Parse(inputs[2]);
visited = new bool[m, n];
for(int i = 0; i < k; ++i)
{
inputs = Console.ReadLine().Split();
list.Add(new ColoringPos(Int32.Parse(inputs[0]), Int32.Parse(inputs[1]), Int32.Parse(inputs[2]), Int32.Parse(inputs[3])));
}
for(int i = 0; i < list.Count; ++i)
{
var cor = list[i];
for(int j = cor.coloringStartPosX; j < cor.coloringEndPosX; ++j)
{
for(int k = cor.coloringStartPosY; k < cor.coloringEndPosY; ++k)
{
visited[j,k] = true;
}
}
}// 모눈종이 색칠하기
for(int i = 0; i < visited.GetLength(0); ++i)
{
for(int j = 0; j < visited.GetLength(1); ++j)
{
if(visited[i, j] == false)
{
int posX = i;
int posY = j;
BFS(i,j);
}
}
}
Console.WriteLine(sectorList.Count);
sectorList.Sort();
for (int i = 0; i< sectorList.Count; ++i)
{
Console.Write(sectorList[i] + " ");
}
}
public void BFS(int curPosX, int curPosY)
{
Queue<Tuple<int,int>> q = new Queue<Tuple<int, int>>();
int sector = 0;
q.Enqueue(new Tuple<int, int>(curPosX, curPosY));
++sector;
while (q.Count > 0)
{
var deq = q.Dequeue();
int posX = deq.Item1;
int posY = deq.Item2;
if (visited[posX, posY] == true)
continue;
visited[posX, posY] = true;
for(int i = 0; i < 4; ++i)
{
int newPosX = posX + dx[i];
int newPosY = posY + dy[i];
if (isCheckSafeArea(newPosX, newPosY) == false)
continue;
if (visited[newPosX, newPosY] == true)
continue;
if (q.Contains(new Tuple<int, int>(newPosX, newPosY)) == true)
continue;
q.Enqueue(new Tuple<int,int>(newPosX, newPosY));
++sector;
}
}
sectorList.Add(sector);
}
public bool isCheckSafeArea(int posX, int posY)
{
if (posX < 0 || posX > (m - 1) || posY < 0 || posY > (n - 1))
return false;
return true;
}
}
}
코드 결과
