https://www.acmicpc.net/problem/2583
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
2583, 영역 구하기
[ 난이도 : 실버 1 ]
이번 문제는 그래프 이론과 DFS 를 사용해서 풀이해보겠다.
눈금이 그어진 영역을 제외한 모든 영역의 사이즈 (영역 하나의 넓이가 1) 를 구하면 쉽게 풀이할 수 있는 문제이다.
# Process
main
: 입력받은 값의 영역을 모두 true 로 표기해서 눈금이 그어진 영역을 표시해준다.
M = scan.nextInt();
N = scan.nextInt();
K = scan.nextInt();
area = new boolean[M][N];
while(K-- > 0)
{
int x1 = scan.nextInt();
int y1 = scan.nextInt();
int x2 = scan.nextInt();
int y2 = scan.nextInt();
for(int i=y1; i<y2; i++)
{
for(int j=x1; j<x2; j++)
{
area[i][j] = true;
}
}
}
dfs
: 눈금이 그어지지 않은 좌표를 찾아 이어진 영역의 사이즈, 즉 dfs 호출 회수를 list 에 넣어주면 된다.
static void pro()
{
for(int i=0; i<M; i++)
{
for(int j=0; j<N; j++)
{
if(!area[i][j])
{
ans = 0;
dfs(i,j);
list.add(ans);
}
}
}
sb.append(list.size()+"\n");
Collections.sort(list);
for(int k: list)
{
sb.append(k+" ");
}
System.out.println(sb.toString());
}
static void dfs(int x, int y)
{
area[x][y] = true;
ans++;
for(int k=0; k<4; k++)
{
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if(nx<0 || ny<0 || nx>=M || ny>=N) continue;
if(area[nx][ny]) continue;
dfs(nx, ny);
}
}
전체 코드
: 위의 과정을 통해 쉽게 답을 구할 수 있다.
static int M,N,K, ans;
static boolean[][] area;
static ArrayList<Integer> list = new ArrayList<>();
static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
static void input()
{
M = scan.nextInt();
N = scan.nextInt();
K = scan.nextInt();
area = new boolean[M][N];
while(K-- > 0)
{
int x1 = scan.nextInt();
int y1 = scan.nextInt();
int x2 = scan.nextInt();
int y2 = scan.nextInt();
for(int i=y1; i<y2; i++)
{
for(int j=x1; j<x2; j++)
{
area[i][j] = true;
}
}
}
}
static void pro()
{
for(int i=0; i<M; i++)
{
for(int j=0; j<N; j++)
{
if(!area[i][j])
{
ans = 0;
dfs(i,j);
list.add(ans);
}
}
}
sb.append(list.size()+"\n");
Collections.sort(list);
for(int k: list)
{
sb.append(k+" ");
}
System.out.println(sb.toString());
}
static void dfs(int x, int y)
{
area[x][y] = true;
ans++;
for(int k=0; k<4; k++)
{
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if(nx<0 || ny<0 || nx>=M || ny>=N) continue;
if(area[nx][ny]) continue;
dfs(nx, ny);
}
}
public static void main(String[] args)
{
input();
pro();
}
: )