[자바] 백준 27157, 26081 - GGANALi, 곰곰이와 GGANALi (java)

 문제 : boj27157, boj26081

... (생략)

---

 

필요 알고리즘 개념

• 트리, 구현
  
  • 기본적으로 트리 구조를 만들고 탐색할 줄은 알아야 한다. 하지만 이것대문에 플래인건 아니고, 그냥 구현이 복잡해서 플래티어이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  RPG Extreme 문제가 생각나는 구현 플래 문제이다. 트리구조로 구현해야 하므로 RPG Extreme보단 구현 난이도가 좀 더 높은 것 같다. 다만 개념적으로는 딱히 꼬이는 부분 없이 글에 써진 것 그대로 이해하기 편한편이라 좀 더 정리하기가 쉬웠다. 27157, 26081은 동일한 문제인데 27157이 더 어려운 문제이다(Touch 추가 등).

 

  일단 설계 없이 그냥 짜기엔 디버깅 난이도가 너무 높아진다. 따라서 기본적인 객체지향 설계는 필요하다. 다만 알고리즘 문제 풀 때는 너무 객체지향적으로 설계하면 오히려 어려워지는 경우가 많다(차후 변경을 생각하지 않고 만들 수 있으므로). 아무튼 그래서 로직은 절차지향적으로 짜면서, 구현이 편하게 하기 위해 객체지향적인 부분들을 사용했다.

 

  쌩구현 문제로 코드첨부는 의미가 없을 것 같아 넣지 않았다. 내 경우엔 아래와 같이 클래스를 나눠 풀었다.

- GGANALi : 전체적인 프로그램 흐름을 잡는 메인 클래스 (Main 클래스는 GGANALi를 실행만 함)

 

- Order : 입력으로 주어진 명령어들의 부모클래스이다. New, Add 등의 명렁어들은 Order를 상속받아 입력값으로 인스턴스 변수들을 세팅하는 initParameter()과 각 명령어의 실제 동작에 해당하는 process()를 구현해주면 된다.

 

- Actor : 각 Actor들의 정보를 가지고 있고, Order 들에서 공통적으로 사용할 수 있는 함수들을 수행한다. 기본적으로 각 속성들이 존재하고, 자식에 해당하는 child를 가진다. 부모도 항상 1개이므로 parent라는 변수로 따로 두었다.

 

- ActorStorage : DI로 Order에게 Actor를 넣어주면 더 좋겠지만, 코드가 복잡해지므로 이녀석을 두어서 모든 Actor들을 관리하게 해줬다.

 

- Vector : Vector2 형식의 입력값을 담기위한 클래스이다.

 

- New, Add, Remove, Unparent, SetProperty, GetProperty, Touch : Order를 상속받아 각 명렁어의 실제 구현을 작성하기 위한 클래스이다. 예를들어 Unparent는 다음과 같다.

 

 

 

  실제 process 자체는 절차지향으로 짜더라도, 설계를 객체지향 개념을 좀 넣어서 짜주면 확실히 구현하기 편하다. 이 문제에서 제일 까다로운 부분은 'Touch'의 결과를 출력하는 부분이었다. 마지막에 최종 맵의 색상을 출력하는 부분은 Touch의 결과로 나온 해당 위치의 Actor에서 색상만 출력하는 식으로 WxH번 터치해서 알아냈다. 그러니 Touch 구현이 가장 난이도가 높은 부분이었다. 가장 핵심이 되는 트리 탐색 코드는 아래와 같았다. 내 경우엔 이전에 보던 화면을 Rectangle로 상하좌우 좌표를 모두 나타내서 구현했다. (xs : 작은쪽 x좌표, xe : 큰쪽 x좌표, ys : 작은쪽 y좌표, ye : 큰쪽 y좌표)

- cur : 현재 보고 있는 Actor

- parent : 부모가 만드는 사각형

- clip : CLIP_CHILD에 따라 줄어든, 현재 실제로 화면상에 출력 가능한 부분의 사각형

public void search(Actor cur, Rectangle parent, Rectangle clip) {
    if (clip.xs > touchX || clip.xe < touchX || clip.ys > touchY || clip.ye < touchY) return;
    // 터치할 위치가 이미 화면 밖이라면 더 볼 필요가 없다.

    int anchorX = cur.position.x + (cur.parentOrigin.x == 0 ? parent.xs : parent.xe);
    int anchorY = cur.position.y + (cur.parentOrigin.y == 0 ? parent.ys : parent.ye);
    // 현재 보고 있는 Actor의 ANCHOR 좌표
    
    Rectangle curRect = createRectangle(anchorX, anchorY, cur);
    Rectangle curClip = clip;
    if (cur.clipChild == 1) {
        curClip = createClipRect(clip, curRect);
    }
    // CLIP_CHILD 속성이라면 그에 맞춰 현재 볼 수 있는 화면의 크기를 조정해준다.

	// cur.child.size()-1로 마지막 자식부터 보는 이유는, 어차피 마지막 자식부터 보다가 해당 Touch 좌표에
    // 맞는게 있다면 그걸 택하고 더이상 진행 안해도 되기 때문이다.
    // 주의점이 있다면 자식이 부모의 위에 화면이 올라오므로, 현재 보고 있는 cur에 대해
    // Touch 좌표인지 확인하기 전에 재귀적으로 자식들부터 진행해야 한다.
    for (int i = cur.child.size()-1; searchResult == null && i >= 0; i--) {
        Actor next = cur.child.get(i);
        search(next, curRect, curClip);	// 자식들쪽으로 계속 진행
    }

    if (searchResult != null)
        return;
    if (curRect.contains() && curClip.contains() && (cur.sensitive == 1 || !checkSensitiveDuringSearch))
        searchResult = cur;	// contains()는 현재 터치 좌표를 포함하는지 보는 것이다. 만족하는 경우 Touch의 결과가 현재 보고 있는 Actor이다.
}