문제
모눈종이에 그려진 직사각형을 제외한 나머지 영역의 개수와 그 크기를 오름차순으로 출력하는 문제이다.
접근
처음에 들었던 생각은 주어진 그림을 2차원 배열로 옮겨서 풀면 되겠다고 생각했다.
하지만 입력 값에 주어진 수는 좌표이기 때문에 2차원 배열의 행과 열로 주어진 값 그대로 옮기기는 불가능 하다는 생각과 배열은 좌상단에서 우하단으로 뻗어가는 구조이고, 모눈종이는 좌하단에서 우상단으로 뻗어가는 구조라는 생각이 들었다.
첫번째로 주어진 좌표를 배열의 좌표로 변환하는 방법을 생각했다.
위와 같은 모눈종이이자 배열인 도형이 있을 때, 문제의 조건에 따라서 사각형을 배치하면 이런 식으로 될 것이다.
0 1 3 2 의 사각형을 그렸다.
이때 실제로 칠해진 곳은 1,0 에서 1,2까지가 그려졌다.
이 그림을 보고 사각형을 칠하기 위해선 아래처럼 칠하면 되겠다고 생각했다.
for(int x = x1, x < x2; x++)
for(int y = y1, y<y2; y++)
array[y][x] = OO
그리고 두 번째인 2차원 배열과 모눈종이의 방향 차이는, 실제로 별로 상관이 없다고 바로 생각이 들었다.
위의 식을 활용해서 코드를 작성하기 시작했다.
구현
사용 변수
boolean[][] visited <- 이미 bfs로 찍었거나 사각형이 배치된 경우위의 식을 활용해서 사각형 배치하기
for (int i = 0; i < nOfR; i++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
for (int j = x1; j < x2; j++) {
for (int k = y1; k < y2; k++) {
visited[k][j] = true;
}
}
}
각 영역의 크기 구하기
public int bfs(int row, int col, int maxR, int maxC){
Queue<Cor> q = new LinkedList<>();
q.add(new Cor(row,col));
visited[row][col] = true;
int count = 1;
while (!q.isEmpty()) {
Cor cor = q.poll();
count +=move(cor.x -1,cor.y,maxR,maxC ,q);
count +=move(cor.x +1,cor.y,maxR,maxC ,q);
count +=move(cor.x ,cor.y-1,maxR,maxC ,q);
count +=move(cor.x,cor.y+1,maxR,maxC ,q);
}
return count;
}
public int move(int row, int col, int mr, int mc, Queue<Cor> q){
if(row >= 0 && row < mr && col >= 0 && col < mc){
if (!visited[row][col]) {
q.add(new Cor(row,col));
visited[row][col] = true;
return 1;
}
}
return 0;
}
결과
BFS를 활용하여 큰 어려움 없이 해결한 문제같다.
전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
/*
https://www.acmicpc.net/problem/2583
그래프 탐색 실버 1 */public class P2583 {
boolean[][] visited;
public void solution() throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int nOfR = Integer.parseInt(st.nextToken());
visited = new boolean[r][c];
for (int i = 0; i < nOfR; i++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
for (int j = x1; j < x2; j++) {
for (int k = y1; k < y2; k++) {
visited[k][j] = true;
}
}
}
List<Integer> counts = new ArrayList<>();
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if(visited[i][j])
continue;
counts.add(bfs(i,j,r,c));
}
}
Collections.sort(counts);
printAnswer(counts);
}
private void printAnswer(List<Integer> counts) {
StringBuilder sb = new StringBuilder();
sb.append(counts.size()).append("\n");
for (Integer count : counts) {
sb.append(count).append(" ");
}
System.out.println(sb);
}
public int bfs(int row, int col, int maxR, int maxC){
Queue<Cor> q = new LinkedList<>();
q.add(new Cor(row,col));
visited[row][col] = true;
int count = 1;
while (!q.isEmpty()) {
Cor cor = q.poll();
count +=move(cor.x -1,cor.y,maxR,maxC ,q);
count +=move(cor.x +1,cor.y,maxR,maxC ,q);
count +=move(cor.x ,cor.y-1,maxR,maxC ,q);
count +=move(cor.x,cor.y+1,maxR,maxC ,q);
}
return count;
}
public int move(int row, int col, int mr, int mc, Queue<Cor> q){
if(row >= 0 && row < mr && col >= 0 && col < mc){
if (!visited[row][col]) {
q.add(new Cor(row,col));
visited[row][col] = true;
return 1;
}
}
return 0;
}
class Cor{
int x;
int y;
public Cor(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws Exception {
new P2583().solution();
}
}
```
