[Kotlin, P4] 백준 10000번 원 영역

출처: unsplash.com

 

원 영역(10000번)

Platinum 4

#자료 구조 #정렬 #기하학 #스택

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

 

문제 내용

 

문제 접근

우선 문제 이해부터 해보자.

간단하다.

원을 x축에 구성하고 난 후, 영역을 세면 된다. 영역의 개수는 다음과 같이 세면 된다.

출처: https://wonyoung2257.tistory.com/79

 

원의 영역과 원끼리 접하면서 나뉜 영역도 생각해야 하고, 원 바깥의 영역도 처리해야 한다.

원끼리 접하면서 나뉘게 되는 영역을 나누는 방법을 생각해야 하기 때문에 어렵다.

 

초기 구현 아이디어를 떠올리기 위해 아래의 블로그를 참고해서 구현했다.

https://wonyoung2257.tistory.com/79

[백준 python] 10000번 원 영역

 

위 사진의 원 구조를 괄호로 표현하면 (()())와 같은 형태가 된다.

사진의 경우에는 원이 모두 접해 있지만 원이 접해있지 않는 경우도 따로 처리를 해주어야 한다.

원이 접했는지 파악하는 방법은 이전 원과 좌표가 동일하면 두 원이 접해있다는 뜻이다.

 

원이 접해있지 않을 때는 다음과 같은 경우가 있다.

출처: https://wonyoung2257.tistory.com/79

 

원이 접해있지 않아서 영역이 나뉘지 않는다는 것을 확인할 수 있다.

그러면 로직을 어떻게 구현해야 할까?

 

1. 원의 좌표를 담은 리스트 생성

원의 좌표 정보를 담는 리스트를 생성해 준다. 원의 x축에 접하는 두 개의 좌표를 넣어준다 왼쪽은 여는 괄호("(")를, 오른쪽은 닫는 괄호(")")를 넣어 준다.

 

2. 리스트 정렬

받은 리스트를 정렬한다.

좌표 순으로 우선 정렬하고, 닫힌 괄호(")")가 먼저 오게 정렬한다.

 

3. 원이 끝날 때의 처리(스택 사용)

이제 정렬된 리스트를 스택에 집어넣어 주어야 한다.

스택에는 원의 위치와 괄호 string, 이전 점과 접하는지 확인하는 데이터를 넣어 주어야 한다.

이제 리스트를 순회하면서 2가지의 경우를 처리해 준다.

 

3-1. 여는 괄호가 온 경우

스택의 최상단 데이터의 좌표와 비교해서 같은 좌표이면 peek 데이터의 접합 여부를 true로 설정한다.

그리고 스택에 데이터를 넣는다.

 

3-2. 닫는 괄호가 온 경우

만약 현재 스택의 최상단 데이터의 접합 여부가 true라면 영역 카운트를 2개를 늘려주고 아니면 1개를 늘려준다.

그리고 스택 데이터를 pop 한다.

 

다음 데이터의 값과 현재 보고 있는 값의 좌표가 다르면 스택의 최상단 데이터의 접합 여부를 false로 설정한다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.Stack

private data class Circle(
    val position: Int,
    val circle: String,
    var isContact: Boolean
)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val point = mutableListOf<Pair<Int, String>>()

    for (i in 1 .. n) {
        val (x, r) = readLine().split(" ").map { it.toInt() }
        point.add(Pair(x - r, "("))
        point.add(Pair(x + r, ")"))
    }

    point.sortByDescending { it.second }
    point.sortBy { it.first }

    var area = 1
    val stack = Stack<Circle>()
    for (i in 0 until point.size) {
        val current = point[i]

        if (i == 0) stack.add(Circle(current.first ,current.second, false))
        else {
            when (current.second) {
                "(" -> {
                    // 이전 위치와 같은 위치면 접해있는 원임.
                    if (stack.isNotEmpty() && stack.peek().position == current.first) stack[stack.lastIndex].isContact = true
                    stack.add(Circle(current.first, current.second, false))
                }
                ")" -> {
                    if (!stack.peek().isContact) area++
                    else area += 2
                    stack.pop()

                    if (i + 1 in 0 until point.size) {
                        val next = point[i + 1]
                        // 다음 원과 접해 있지 않을 때
                        if (stack.isNotEmpty() && next.first != current.first) stack[stack.lastIndex].isContact = false
                    }
                }
            }
        }
    }

    println(area)
}

 

문제 풀이

스택에 값을 넣을 data class를 생성해 준다.

data class에는 좌표, 원의 구성(괄호 string), 접합 여부로 이루어져 있다.

 

입력값에 따라 point 리스트를 구성해 준다. point 리스트는 pair로 구성해 주었다.

첫 번째 값이 좌표, 두 번째 값이 원의 구성 데이터(괄호 string)이다.

 

구성한 point list를 괄호순으로 정렬해 주고 그다음 좌표별로 정렬해 준다.

그래야 닫는 괄호가 먼저 오게 되고 우선순위가 높은 좌표순을 나중에 설정함으로써 좌표 우선 정렬이 가능해진다.

 

초기 area 데이터는 1로 설정해 준다. 그 이유는 원 바깥의 영역을 포함하기 위해서이다.

Circle data class 데이터를 담는 stack을 만들어 준다.

point list를 반복해 준다.

첫 반복에는 무조건 여는 괄호가 들어오기 때문에 stack에 값을 넣어주면서 시작한다.

두 번째 반복에서부터 들어오는 괄호에 따라 판단해서 로직을 적용한다.

 

여는 괄호가 들어오게 되면 이전의 원 안에 작은 원이 들어온다는 뜻이 된다.

들어온 데이터의 좌표가 stack의 최상단 데이터와 동일하다면 두 원이 접해있다는 뜻이 된다.

이러면 큰 원에 영역이 2개가 생길 가능성이 있다. 그래서 큰 원의 접합 여부를 true로 설정한다.

 

닫는 괄호가 들어오게 되면 이제 구역의 개수를 세주면 된다.

닫는 괄호가 들어왔을 때 무조건 stack에는 여는 괄호 데이터가 들어있게 된다.

여는 괄호 데이터의 접합 여부를 확인해 준다. true이면 2를 false면 1개의 영역이 있다는 뜻이다.

그리고 여는 괄호 데이터를 stack에서 1개를 제거한다.

 

그리고 다음에 들어오게 될 데이터와 현재 데이터의 좌표를 비교해 준다. 다음 원과 좌표가 다른 경우에는 다음 원과 접해있지 않는다는 뜻이기 때문에 접합 여부를 false로 설정해 준다.

 

그림으로 문제 로직을 설명해 주겠다.

출처: https://wonyoung2257.tistory.com/79

 

이 그림으로 설명해 보겠다. 편의를 위해 가장 큰 원을 2번 원, 중간 원을 3번 원, 작은 원을 4번 원으로 칭하겠다.

1. 우선 먼저 들어오게 되는 2번 원의 좌표를 확인한다. 여는 괄호로 들어오기 때문에 circle에 isContact를 false로 설정하고 stack에 넣는다.
   stack: [Circle(2번 원, "(", false)], area: 1
2. 다음으로 들어오는 데이터는 3번 원의 여는 괄호 데이터이다. 현재 좌표와 stack에 최상단 데이터와의 좌표가 같다. 그래서 현재 stack의 접합 여부를 true로 바꿔준 다음 stack에 값을 넣는다.
   stack: [Circle(2번 원, "(", true), Circle(3번 원, "(", false)], area: 1
   
3. 3번 원의 닫는 괄호가 들어왔다. 현재 stack의 최상단 데이터의 접합 여부를 확인한다. false이므로 area에 1을 더해준다. 그리고 stack의 값 1개를 삭제한다.
   stack: [Circle(2번 원, "(", true)], area: 2
   
4. 다음 원의 좌표를 확인한다(4번 원의 여는 괄호 데이터). 다음 원의 좌표 데이터와 현재 보고 있는 데이터(3번 원의 닫는 괄호)가 다르기 때문에 stack에 최상단 데이터의 접합 여부를 false로 변경한다.
   stack: [Circle(2번 원, "(", false)], area: 2
   
5. 4번 원의 여는 괄호가 들어왔다. 현재 stack의 최상단 데이터와 현재 데이터의 좌표를 비교한다. 좌표값이 다르다. 그래서 stack의 최상단 데이터의 접합 여부를 false로 변경한다. 그리고 stack에 넣어 준다.
   stack: [Circle(2번 원, "(", false), Circle(4번 원, "(", false)], area: 2
   
6. 4번 원의 닫는 괄호가 들어왔다. 현재 stack의 데이터의 접합 상태를 확인한다. false이므로 area에 1을 더한다. 그리고 stack의 데이터를 삭제한다.
   stack: [Circle(2번 원, "(", false)], area: 3
   
7. 다음 데이터는 2번 원의 닫는 괄호이다. 다음 데이터와 현재 데이터(4번 원의 닫는 괄호)의 좌표를 비교한다. 다르기 때문에 stack 데이터의 접합 여부를 false로 설정해 준다.
   stack: [Circle(2번 원, "(", false)], area: 3
   
8. 마지막 데이터인 2번 원의 닫는 괄호가 들어왔다. 현재 stack의 최상단 데이터의 접합 상태를 확인한다. false이므로 area에 1을 더해준다. 그리고 stack의 데이터를 삭제한다.
   stack: [], area: 4
   
9. stack이 비어있다는 것과, 다음 데이터가 없기 때문에 다음 데이터와 비교하는 로직은 수행되지 않는다.
10. 반복문 종료 후 최종 area를 출력하면 4가 된다.

 

 

문제 해결 과정

문제 접근 방식을 보고도 구현하는 게 어려워서 위에 언급한 분의 포스팅을 참고해서 로직을 구성해 주었다.

내 나름대로 로직 해석을 통해 조금이라도 다르게 구현하고 싶었지만 그게 잘 안되더라.

로직이 돌아가는 과정을 글로 적어보니까 정리도 되고 이해가 훨씬 더 잘 되었다.

좌표를 불러와 정렬하고, stack을 사용해 영역을 세야 하는 어려운 문제였다. 플래티넘인 이유가 있구나 역시.