오늘 문제는 로고입니다.
1. 문제요약
- 거북이는 처음엔 0,0에 위치하고, 펜을 내린 상태입니다.
- 문제에서는 n개의 직사각형이 주어집니다.
2-1. ( x1, y1, x2, y2 )의 좌표값 형태로 주어지며, ( x1, x2) 는 한 꼭짓점의 좌표이고 ( x2, y2 )는 해당 꼭짓점의 대각선 방향의 좌표입니다. - 거북이는 펜 올리기, 펜 내리기, 오른쪽 돌기, 왼쪽 돌기를 수행합니다.
- 문제에서 주어진 직사각형을 그리기 위해 거북이가 펜을 내리는 최소 횟수를 구하세요.
2. 접근법
-
거북이는 처음엔 0,0에 위치하고, 펜을 내린 상태입니다.
-
겹치는 선분 검출: 새로 입력받은 사각형의 선분이 기존 Set에 있는지 contains로 확인하여 겹치는지 검사합니다.
: 이때 동등성 검사로 진행한다 -
겹침 여부에 따라 PU 감소: 기존에 있는 점과 겹치면 isContain을 true로 설정하고, 사각형의 총 개수(PU)를 줄입니다.
-
원점 체크: (0, 0)을 Set에 미리 추가해 원점과 연결된 사각형을 쉽게 감지합니다.
3. 코드
코드는 다음과 같습니다.
3-1. Point 클래스
static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Point point = (Point) o;
return x == point.x && y == point.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}3-2. 전역변수와 main 함수
static Set<Point> squaresPoint;
static int squareNum;
static int PU;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
squareNum = Integer.parseInt(br.readLine());
PU=squareNum;
squaresPoint = new HashSet<>();
squaresPoint.add(new Point(0,0));
for(int i=0; i<squareNum; i++){
st = new StringTokenizer(br.readLine());
findLine(Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()));
}
System.out.println(PU);
}3-3. findLine 함수
static void findLine(int x1, int y1, int x2, int y2) {
int bigX = Math.max(x1, x2);
int bigY = Math.max(y1, y2);
int smallX = Math.min(x1, x2);
int smallY = Math.min(y1, y2);
boolean isContain = false;
// 가로 라인 넣기
for (int x = smallX+1; x < bigX; x++) {
Point point1 = new Point(x, bigY);
Point point2 = new Point(x, smallY);
if (squaresPoint.contains(point1) || squaresPoint.contains(point2)) {
isContain=true;
}
//점 Set에 추가
squaresPoint.add(point1);
squaresPoint.add(point2);
}
// 세로 라인 넣기
for (int y = smallY; y <= bigY; y++) {
Point point1 = new Point(smallX, y);
Point point2 = new Point(bigX, y);
if (squaresPoint.contains(point1) || squaresPoint.contains(point2)) {
isContain=true;
}
//점 Set에 추가
squaresPoint.add(point1);
squaresPoint.add(point2);
}
if(isContain) PU--;
} 
3. 형님들 코드
도저히 못 풀겠어서 그냥 형님들 코드를 참고했다.
형님들은 해당 문제를 union-find로 푸셨다.
3-0. 변수 설명
3-1. main 함수 설명
- 입력을 받아 각 사각형을 처리하고, 사각형이 서로 겹치면 그룹을 합칩니다.
- setSquare 메서드를 호출하여 각 사각형의 좌표를 설정하고 겹침 여부를 확인합니다.
- zero 플래그가 설정되면 결과에서 하나를 빼줍니다.
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
map = new int[SIZE][SIZE];
p = new int[SIZE];
for (int i = 0; i < SIZE; i++) {
p[i] = i;
}
ans = N;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken())+PLUS;
int y1 = Integer.parseInt(st.nextToken())+PLUS;
int x2 = Integer.parseInt(st.nextToken())+PLUS;
int y2 = Integer.parseInt(st.nextToken())+PLUS;
num++;
setSquare(new Square(x1, x2, y1, y2));
}
if (zero) ans--;
System.out.println(ans);
}3-2. setSquare 함수
- 사각형의 테두리를 따라 순회하며, 겹치는 사각형이 있는지 확인합니다.
- 테두리 좌표를 업데이트하고, 이미 다른 사각형에 속한 경우 Union-Find 연산을 통해 그룹을 합칩니다.
- zeroCheck를 호출하여 (500, 500)이 포함되는지를 검사합니다
public static void setSquare(Square square) {
for (int i = square.y1; i <= square.y2; i++) {
//현재 사각형의 테두리 좌표가 이미 다른 사각형에 속하는지 확인.
if (map[square.x1][i] != 0 && map[square.x1][i] != num) {
//두 사각형이 서로 다른 그룹에 속해 있다면, 그룹을 합쳐 총 그룹의 수를 감소시킴.
if (findSet(map[square.x1][i]) != findSet(num)) {
ans--;
union(map[square.x1][i], num);
}
}
if (map[square.x2][i] != 0 && map[square.x2][i] != num) {
if (findSet(map[square.x2][i]) != findSet(num)) {
ans--;
union(map[square.x2][i], num);
}
}
map[square.x1][i] = num;
map[square.x2][i] = num;
zeroCheck(square.x1, i);
zeroCheck(square.x2, i);
}
for (int i = square.x1; i <= square.x2; i++) {
if (map[i][square.y1] != 0 && map[i][square.y1] != num) {
if (findSet(map[i][square.y1]) != findSet(num)) {
ans--;
union(map[i][square.y1], num);
}
}
if (map[i][square.y2] != 0 && map[i][square.y2] != num) {
if (findSet(map[i][square.y2]) != findSet(num)) {
ans--;
union(map[i][square.y2], num);
}
}
map[i][square.y1] = num;
map[i][square.y2] = num;
zeroCheck(i, square.y1);
zeroCheck(i, square.y2);
}
}3. union&Find
Union-Find 알고리즘의 동작 방식 요약
1.초기 상태:
- 각 원소는 자신을 대표로 하며, p[i] = i로 초기화됩니다.
2.findSet 함수 호출:
- 입력된 원소가 속한 집합의 대표 원소를 찾아 반환합니다.
3.union 함수 호출:
- 두 집합을 병합할 때, 두 대표 원소를 하나로 만듭니다.
//입력된 x가 속한 집합의 대표 원소(루트 노드)를 찾는 역할.
public static int findSet(int x) {
if (x == p[x]) return x; //본인이 부모면 반환
return p[x] = findSet(p[x]);
}
public static void union(int x, int y) {
//1. findSet(x)와 findSet(y)를 호출하여 각각의 대표 원소를 찾은 후
//2. findSet(y)의 대표 원소를 findSet(x)의 대표 원소로 설정하여 두 집합을 하나로 만든다.
p[findSet(y)] = findSet(x);
//y의 루트 노드가 x의 루트 노드를 가리키도록 함으로써 두 집합을 병합하는 것
} 