| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 46 | 16 | 13 | 30.233% |
곰곰컵 문제를 몇 개 풀다 보면 느끼는 것이 있을 것이다. 바로 “잘 알려진” 문제들이라는 것이다.
곰곰컵은 쉽고 재밌는 애드혹 대회를 모토로 문제들을 제작하고 있다. 이 컨셉에 감동 받은 pichulia는 알고리즘을 모르더라도 누구나 쉽게 구현할 수 있는 문제를 만들고 싶어 이 문제를 출제하였다. 이 문제는 알고리즘과 관련된 사전 지식이 전혀 없어도 Naive하게 풀 수 있기 때문에 아주 좋은 문제라고 pichulia는 자신한다.
pichulia가 회사에서 작업하는 오픈소스 프로젝트의 이름은 DALi (달리)이다. 이는 Dynamic Animation Library의 약자로, 애니메이션을 지원하는 2D / 3D UI framework의 역할을 수행하는 라이브러리이다.
이제 이 DALi 라이브러리의 기능 일부를 직접 구현해보자! DALi 라이브러리의 기능을 전부 구현하기에는 양이 방대하니, 기능 일부를 열화시킨 GomGom Algorithmically NAive Library, 줄여서 GGANALi (까나리)를 정의하고 구현해보자. 실제 DALi 라이브러리와 용어나 동작이 다를 수 있음에 유의하자.
GGANALi는 크기/위치/색상 정보를 가진, Actor 라고 불리는 컴포넌트를 트리 구조 형태로 배치해서 UI를 구성한다. 이 Actor는 직사각형 형태이며 POSITION, SIZE, COLOR 등의 속성 값을 가진다.
각 Actor는 이름을 가지고 있다. 특별히 Window라는 이름을 가진 Actor는 실제 화면을 나타내는 Actor로, 항상 트리의 루트이다. Window의 가로 크기 $W$와 세로 크기 $H$는 입력으로 주어지며, 이후 변경되지 않는다. 이 Window Actor의 자식으로 들어온 Actor들은 Scene On 되었다고 표현하며, 이러한 Actor들만이 화면에 그려질 것이다.
Actor를 실제 Window에 그릴 때에는, Window를 루트로 하는 트리 구조를 Pre-order로 순회하면서 화면을 채워나간다. Actor가 화면을 채울 때에는, Actor의 영역에 해당하는 직사각형 모양으로 화면의 색을 COLOR색으로 바꿔준다. 이 때 나중에 화면을 채우는 Actor는 이전에 채운 Actor 의 색을 덮어씌운다. 따라서 최종적으로는 트리의 가장 마지막에 위치한 Actor가 화면상에서는 가장 위에 놓여진 것처럼 보이게 된다.
위에서 잠깐 나왔지만, Actor는 속성을 몇 가지 가지고 있다. 속성마다 값의 타입이 따로 정해져 있다. 이 속성의 값은 자유롭게 바꾸거나 값을 가져올 수 있다. 단, Read-only 속성은 값을 변경할 수 없다. 예를 들어 SIZE 속성은 Vector2 타입의 값이다. 처음에 아무런 값을 설정하지 않은 경우는 기본적으로 (0ドル,ドル 0ドル$) 값을 가지지만, SetProperty 명령어를 통해 이 값을 (4ドル,ドル 5ドル$)으로 변경할 수 있다. 별도로 설정하지 않은 경우는 기본값이 설정된다. Window 는 특별한 Actor로, 속성을 별도로 설정하지 않아도 POSITION, PARENT_ORIGIN, ANCHOR_POINT 는 (0ドル,ドル 0ドル$), SIZE 는 ($W,ドル $H$), COLOR 는 0ドル,ドル SENSITIVE 와 CLIP_CHILD 는 1ドル$ 의 값을 가진다.
Actor의 속성은 Read-only 속성 1개와, 값을 바꿀 수 있는 속성 7개로 총 8개가 있다. 각 속성의 타입과 기본값은 이 문제 지문의 가장 아래의 표를 참고하자.
SIZE, POSITION, PARENT_ORIGIN, ANCHOR_POINT는 모두 2차원 ($x,ドル $y$) 꼴의 좌표 형태로 표현된다. SIZE의 $x$는 가로(Width), $y$는 세로(Height)를 의미하고, 화면을 기준으로 오른쪽방향이 $+X$축 방향이고, 아래방향이 $+Y$축 방향이다.
Actor의 위치는 모두 부모 Actor에 대한 상대적인 위치로 계산된다. 이 때 상대적인 위치를 결정할 때 사용되는 속성으로 PARENT_ORIGIN과 ANCHOR_POINT이 있다.
PARENT_ORIGIN은 현재 Actor의 상대적인 위치의 원점이 될 지점이 부모 Actor의 네 귀퉁이 중 어느 지점이 될 것인지를 나타낸다. $x$ 값이 0ドル$인 경우 현재 Actor의 왼쪽 지점, $x$ 값이 1ドル$ 인 경우에는 현재 Actor의 오른쪽 지점을 의미한다. 비슷하게 $y$ 값이 0ドル$인 경우 현재 Actor 의 위쪽 지점, $y$ 값이 1ドル$인 경우에는 현재 Actor의 아래쪽 지점을 의미한다.
이를 조합하면 상대적인 위치의 원점이 부모 Actor의 네 귀퉁이 중 어느 지점으로 결정될 것인지 알 수 있다. 예를 들어 (0ドル,ドル 0ドル$)인 경우에는 부모 Actor의 왼쪽 위 지점을, (1ドル,ドル 0ドル$)인 경우에는 오른쪽 위 지점, (0ドル,ドル 1ドル$)인 경우에는 왼쪽 아래 지점을 의미한다.
ANCHOR_POINT는 이 원점으로부터 POSITION만큼 떨어진 지점이, 현재 Actor의 네 귀퉁이 중 어느 지점이 될 것인지를 결정한다. 각 값에 따른 귀퉁이 지점은 PARENT_ORIGIN과 같다. 예를 들어 (0ドル,ドル 0ドル$)인 경우에는 현재 Actor 의 왼쪽 위 지점을, (1ドル,ドル 0ドル$)인 경우에는 오른쪽 위 지점, (0ドル,ドル 1ドル$)인 경우에는 왼쪽 아래 지점을 의미한다.
SCREEN_POSITION은 Actor의 배치와 구조에 의해서 자동적으로 결정되는 값이다. Window의 가장 왼쪽 위의 좌표를 (0ドル,ドル 0ドル$)으로 봤을 때, 해당 Actor의 ANCHOR_POINT의 위치를 나타내는 값이다. 자동으로 결정되는 값이기 때문에 SetProperty 명령어로 변경할 수 없다. 만약 Scene On 상태가 아니라면 이 값은 (0ドル,ドル 0ドル$)이다.
COLOR 은 최종적으로 Window에 화면을 그릴 때, 해당 Actor가 화면을 무슨 색으로 칠할지를 결정하는 값이다. 이 문제에서는 색상 정보를 1ドル$이상 9ドル$이하의 정수로 표현해서 사용한다.
SENSITIVE는 0ドル$ 또는 1ドル$ 중 하나의 값을 가진다. 값이 1ドル$인 경우에는 Touch 이벤트에 대한 결과로 선택될 수 있다는 의미이다. 이 값이 0ドル$이면 Touch 이벤트 결과로 선택될 수 없다.
Touch 이벤트는 특정 좌표에서, 화면상에 가장 위에 그려진 Actor부터 차례로 검사를 진행한다. 만약 가장 위에 그려진 Actor의 SENSITIVE 값이 1ドル$ 인 경우 해당 Actor에게 Touch 이벤트가 발생했음을 의미한다. 이렇게 선택된 Actor의 이름을 출력하고 Touch 검사를 종료한다. 만약 SENSITIVE 값이 0ドル$인 경우 Touch 이벤트로 선택되지 못하므로, 그다음으로 위에 그려진 Actor부터 다시 검사를 진행한다.
이 문제에서는 정확한 판정을 위해서 Touch 좌표는 항상 (정수 $+ 0.5,ドル 정수 $+ 0.5$) 좌표에 대한 입력만 주어진다고 가정한다.
CLIP_CHILD는 값이 1ドル$로 설정될 경우 해당 Actor의 자손들은 모두 Actor의 영역으로 잘린 채로 화면에 그려지게 된다. 잘려진 부분은 이후 Touch 이벤트에 대한 처리에서도 제외된다.
이상이 이 GGANALi에서 사용하는 Actor와 속성의 의미, 그리고 트리 구조에 대한 대략적인 설명이다.
이 구조에서 Actor구조를 추가, 제거하는 명령어를 수행하고 속성 값을 확인하는 명령어의 결과도 출력하고, Touch 이벤트 결과, 그리고 최종적으로 화면에 그려진 모습까지 출력해보자.
Actor의 각 속성의 이름과 타입, 기본값 등에 대한 정보는 아래 표에 요약, 정리하였다.
속성 이름
타입
기본값
Read-only
비고
POSITION
Vector2
(0ドル,ドル 0ドル$)
부모 Actor에 대한 ANCHOR_POINT의 상대적인 위치.
SIZE
Vector2
(0ドル,ドル 0ドル$)
Actor의 크기.
COLOR
Int
1ドル$
화면을 채울 때 사용할 색. [1ドル$-9ドル$] 범위의 값만 사용 가능.
PARENT_ORIGIN
Vector2
(0ドル,ドル 0ドル$)
Actor가 생각하는 부모 Actor의 원점을 나타내는 값. 각 $X,ドル $Y$ 값은 0ドル$ 또는 1ドル$ 만 가능하다.
ANCHOR_POINT
Vector2
(0ドル,ドル 0ドル$)
Actor의 위치를 직사각형의 네 귀퉁이 중 어느 지점을 기준으로 계산할지 나타내는 값. 각 $X,ドル $Y$ 값은 0ドル$ 또는 1ドル$ 만 가능하다.
SENSITIVE
Int
1ドル$
현재 Actor가 Touch 이벤트를 받을 것인지 여부를 결정하는 값. 0ドル$ 인 경우 Touch 이벤트의 결과로 해당 Actor가 선택될 수 없다. 0ドル$ 또는 1ドル$ 만 가능하다.
CLIP_CHILD
Int
0ドル$
현재 Actor의 자손 Actor들이 현재 Actor 직사각형을 영역 내에서만 그리도록 할 것인지를 결정하는 값. 0ドル$ 또는 1ドル$ 만 가능하다.
SCREEN_POSITION
Vector2
(0ドル,ドル 0ドル$)
O
해당 Actor의 ANCHOR_POINT가 Window의 (0ドル,ドル 0ドル$)를 기준으로 어느 지점에 위치한지를 나타내는 값. Scene On인 상태에만 정의되며, 만약 Actor가 Scene On 상태가 아니면 (0ドル,ドル 0ドル$)이다.
입력의 첫째 줄에는 Window의 크기를 나타내는 두 정수 $W,ドル $H$가 공백으로 구분되어서 차례로 주어진다.
가로를 나타내는 값 $W$가 $H$보다 먼저 주어짐에 유의하자. (3ドル \le W,ドル $H \le 50$)
두 번째 줄에는 명령어의 개수를 나타내는 정수 $Q$가 주어진다. (3ドル \le Q \le 5,000円$)
이후 총 $Q$개의 명령어가 주어진다. 각 명령어는 한 줄에 하나씩 주어지며, 아래와 같은 형태를 가진다.
예외로, Touch는 [Actor 이름]이 주어지지 않는다.
명령어의 목록과 각 명령어의 인자, 동작은 아래 표를 참고하자.
[Actor 이름]은 알파벳 대소문자와 숫자, 그리고 언더바(_, ASCII 값 95) 로만 구성된 길이 1ドル$이상 20ドル$이하의 문자열이다.
입력으로 들어오는 [Actor 이름]과 [Actor 이름2]은 Window를 제외하고 항상 New 명령어로 정의된 Actor만 들어온다는 것이 보장된다.
Window가 [Actor 이름]으로 등장하는 경우는 Add Window, Remove Window 외에는 주어지지 않는다.
명령어 이름
인자
출력 여부
비고
New
(없음)
이름이 [Actor 이름]인 Actor를 새로 정의한다. 부모 Actor나 자식 Actor는 따로 정의되지 않고, 속성 값은 기본값을 사용한다.
기존에 존재한 적이 없는 Actor 이름이 보장된다.
Add
[Actor 이름2]
[Actor 이름2] Actor를 [Actor 이름]의 자식 Actor로 추가한다. 이후 [Actor 이름2]의 부모 Actor는 [Actor 이름]이 된다.
기존에 [Actor 이름2]에 이미 부모 Actor가 있던 경우에는 [Actor 이름2]의 Unparent 연산이 먼저 수행된 뒤에 Add 연산이 수행된다.
이 연산 이후 [Actor 이름2] Actor는 [Actor 이름] 의 자식 Actor 목록에서 가장 마지막 Actor가된다.
[Actor 이름]이 [Actor 이름2]의 자손 관계인 경우는 주어지지 않는다.
Remove
[Actor 이름2]
[Actor 이름2] Actor를 [Actor 이름] Actor의 자식 Actor 목록에서 제거한다. 제거가 된 이후에는 [Actor 이름2]의 부모 Actor는 없다.
[Actor 이름2] Actor가 [Actor 이름]의 자식이 아니면 아무 일도 일어나지 않는다.
Unparent
(없음)
[Actor 이름] Actor의 부모와의 연결 관계를 끊는다. 아 연산 이후 [Actor 이름] Actor의 부모 Actor는 자식 Actor 목록에서 [Actor 이름] Actor가 지워지며, [Actor 이름] Actor는 부모 Actor가 없다.
기존에 이미 부모 Actor가 없던 경우에는 아무 일도 일어나지 않는다.
SetProperty
[속성 이름] [$V$]
또는
[속성 이름] [$X$] [$Y$]
[Actor 이름] Actor의 [속성 이름] 속성을 [속성 값]으로 변경한다. [속성 이름]의 타입이 Int 인 경우에는 정수 $V$가, Vector2인 경우에는 두 정수 $X,ドル $Y$가 띄어쓰기로 구분되어 주어진다.
각 속성 이름 및 값의 범위는 아래 표와 같다. [속성 이름]으로 SCREEN_POSITION 은 주어지지 않는다.
속성 이름
속성 값 범위
POSITION
$-100,000円 \le X,ドル $Y \le 100,000円$
SIZE
0ドル \le X,ドル $Y \le 100,000円$
COLOR
1ドル \le V \le 9$
PARENT_ORIGIN
0ドル \le X,ドル $Y \le 1$
ANCHOR_POINT
0ドル \le X,ドル $Y \le 1$
CLIP_CHILD
0ドル \le V \le 1$
SENSITIVE
0ドル \le V \le 1$
GetProperty
[속성 이름]
O
[Actor 이름] Actor의 [속성 이름] 속성의 현재 값을 출력한다.
Touch
[$X$] [$Y$]
O
현재 Window에서 ($X$ $+ 0.5,ドル $Y$ $+ 0.5$) 지점에 Touch 이벤트가 일어난다. 0ドル \le X \lt W,ドル 0ドル \le Y \lt H$.
각 명령어가 출력해야하는 값은 출력 항목을 참고하자.
출력이 필요한 명령어에 대해, 해당 명령어에 대응되는 정보를 각 명령어마다 한 줄씩 출력한다.
명령어 이름
출력 형태
비고
GetProperty
[$V$] 또는 [$X$] [$Y$]
출력하는 속성의 타입이 Int인 경우에는 정수 $V$ 1개를, Vector2인 경우에는 각 $X,ドル $Y$ 값을 공백으로 구분하여 출력한다.
Touch
[Actor 이름]
Touch 이벤트가 발생한 지점에 만나게 되는 Actor의 이름을 출력한다. 만약 Touch 이벤트로 만난 Actor가 없는 경우에는 Window 를 출력한다.
CLIP_CHILD=1ドル$ 인 부모 Actor로 인해 잘려 나가거나, SENSITIVE=0ドル$ 인 Actor는 Touch 이벤트의 결과가 될 수 없음에 유의하자.
$Q$개의 명령어가 모두 종료된 뒤에는 현재 Window 에 칠해진 색상을 $H$줄에 걸쳐 출력한다.
구체적으로는 $i$번째 줄의 $j$번째로 Window의 ($i + 0.5,ドル $j + 0.5$) 지점에 대응되는 색상 값을 출력한다. 만약 해당 지점에 Actor가 없는 경우에는 그 자리에 0ドル$을 대신 출력한다. 각 줄의 색상 값 사이에 공백 없이 출력한다.
입력 명령 중에 SCREEN_POSITION, Touch, SENSITIVE, CLIP_CHILD이 등장하지 않는다.
입력 명령 중에 Touch, SENSITIVE, CLIP_CHILD이 등장하지 않는다.
입력 명령 중에 CLIP_CHILD이 등장하지 않는다.
추가 제약사항 없음.
7 5 42 New A Add Window A New B Add Window B SetProperty A POSITION 3 1 SetProperty A SIZE 3 3 SetProperty B POSITION 1 2 SetProperty B SIZE 3 3000 SetProperty B COLOR 2 Touch 3 2 SetProperty B SENSITIVE 0 Touch 3 2 Touch 2 2 New AA SetProperty AA PARENT_ORIGIN 1 1 SetProperty AA ANCHOR_POINT 0 1 SetProperty AA POSITION -3 -1 SetProperty AA SIZE 4 1 SetProperty AA COLOR 3 GetProperty AA SCREEN_POSITION Add A AA GetProperty AA SCREEN_POSITION New AB New AAA Add A AB SetProperty AB PARENT_ORIGIN 1 0 SetProperty AB ANCHOR_POINT 0 0 SetProperty AB POSITION -2 0 SetProperty AB SIZE 3 1 SetProperty AB COLOR 4 Touch 6 1 Add AA AAA SetProperty AAA ANCHOR_POINT 0 1 GetProperty AAA SCREEN_POSITION SetProperty AAA POSITION 2 1 GetProperty AAA SCREEN_POSITION SetProperty AAA SIZE 1 4 SetProperty AAA COLOR 5 Touch 5 1 Touch 5 0 SetProperty A CLIP_CHILD 1 Touch 5 0
B A Window 0 0 3 3 AB 3 2 5 3 AB AAA Window 0000000 0001440 0222350 0222110 0222000
9번째 명령어(SetProperty B COLOR 2)까지 수행한 뒤의 모습
13번째(Touch 2 2) 명령어까지 수행한 뒤의 모습
21번째 명령어(Add A AA)까지 수행한 뒤의 모습
31번째 명령어(Touch 6 1)까지 수행한 뒤의 모습
40번째 명령어(Touch 5 0)까지 수행한 뒤의 모습
42번째 명령어(Touch 5 0)까지 수행한 뒤의 모습
4 3 22 New A New B New azAZ09_ SetProperty A POSITION -1 0 SetProperty B POSITION 2 1 New AA New AB SetProperty AA ANCHOR_POINT 1 1 SetProperty AA POSITION 1 1 SetProperty AA SIZE 2 2 SetProperty AB SIZE 2 2 SetProperty AB COLOR 2 Add Window A Add Window B GetProperty AB COLOR Add A AA Add A AB Add A AA Add A AB Add A AA GetProperty AB SCREEN_POSITION Add B A
2 -1 0 1100 1120 0220
AA Actor 와 AB Actor 의 위치가 계속해서 바뀌다가 최종적으로는 AA 가 가장 위에 그려지게 된다.
SCREEN_POSITION 결과 값이 음수가 될 수 있음에 유의하자.
3 5 3 New window Add Window window SetProperty window SIZE 1 1
100 000 000 000 000
모든 명령어나 Actor 이름, 속성 등은 대소문자를 구분한다.
8 8 30 New A New B Add Window B Add Window A Remove A B Remove Window B Unparent B Add Window B SetProperty A SIZE 3 3 SetProperty B SIZE 3 3 SetProperty B COLOR 3 SetProperty A POSITION 3 1 SetProperty B POSITION 4 5 SetProperty B ANCHOR_POINT 1 1 GetProperty A SCREEN_POSITION GetProperty B SCREEN_POSITION Touch 3 2 Touch 4 2 Touch 3 1 SetProperty B SENSITIVE 0 Touch 3 2 SetProperty B SENSITIVE 1 Touch 3 2 SetProperty B SENSITIVE 0 New BA Unparent BA Add B BA SetProperty BA POSITION -1 -1 SetProperty B CLIP_CHILD 1 GetProperty BA SCREEN_POSITION
3 1 4 5 B A A A B 0 1 00000000 00011100 03331100 03331100 03330000 00000000 00000000 00000000
CLIP_CHILD로 인해 화면에 그려지지 않더라도 부모 관계가 끊긴 것이 아니므로 SCREEN_POSITION 값을 계산할 수 있다.
3 3 12 New New New Add New SIZE New POSITION Add Window Add SetProperty POSITION SIZE 100000 100000 SetProperty SIZE POSITION -100000 -100000 GetProperty SIZE POSITION GetProperty POSITION SIZE GetProperty POSITION POSITION Add Add POSITION Add New Add
-100000 -100000 100000 100000 0 0 000 000 000
5 6 20 New A Add Window A SetProperty A SIZE 2 3 SetProperty A POSITION 1 2 SetProperty A COLOR 2 New B Add A B SetProperty B SIZE 5 4 SetProperty B POSITION 6 -2 SetProperty B COLOR 3 GetProperty B SCREEN_POSITION SetProperty A ANCHOR_POINT 1 0 GetProperty B SCREEN_POSITION SetProperty B PARENT_ORIGIN 0 1 GetProperty B SCREEN_POSITION SetProperty B ANCHOR_POINT 1 1 GetProperty B SCREEN_POSITION SetProperty A PARENT_ORIGIN 1 1 GetProperty B SCREEN_POSITION SetProperty A PARENT_ORIGIN 0 0
7 0 5 0 5 3 5 3 10 9 33333 33333 33333 20000 20000 00000
4 6 39 New A1 New A2 New B3 New B4 SetProperty A1 SIZE 2 2 SetProperty A2 SIZE 2 2 SetProperty B3 SIZE 2 2 SetProperty B4 SIZE 2 2 SetProperty A1 COLOR 1 SetProperty A2 COLOR 2 SetProperty B3 COLOR 3 SetProperty B4 COLOR 4 SetProperty A1 POSITION 1 0 SetProperty A2 POSITION -1 1 SetProperty B3 POSITION 1 2 SetProperty B4 POSITION 1 1 Add A1 A2 Add B3 B4 Add Window A1 Add Window B3 GetProperty A1 SCREEN_POSITION GetProperty A2 SCREEN_POSITION GetProperty B3 SCREEN_POSITION GetProperty B4 SCREEN_POSITION Remove Window B4 GetProperty B4 SCREEN_POSITION Remove Window B3 GetProperty B3 SCREEN_POSITION GetProperty B4 SCREEN_POSITION Unparent B4 Unparent B4 Add Window B3 GetProperty B3 SCREEN_POSITION GetProperty B4 SCREEN_POSITION Add A2 B4 GetProperty B4 SCREEN_POSITION Add Window B4 GetProperty B4 SCREEN_POSITION Add B3 B4
1 0 0 1 1 2 2 3 2 3 0 0 0 0 1 2 0 0 1 2 1 1 0110 2210 2330 0344 0044 0000
PARENT_ORIGIN, ANCHOR_POINT, POSITION 에 대한 설명은 https://dalihub.github.io/docs/native-tutorials/actor 나 https://docs.tizen.org/application/dotnet/guides/user-interface/nui/view/ 의 이미지를 참고하면 좋다.
GGANALi 의 SENSITIVE 속성은 Actor 자기 자신의 이벤트만 막지만, 실제 DALi 에서 SENSITIVE 속성은 자식 Actor의 이벤트도 막는다는 차이점이 있으므로 주의하자.
subtask 1 의 조건을 만족하는 예제는 [예제 3], [예제 5] 번
subtask 2 의 조건을 만족하는 예제는 [예제 2], [예제 6], [예제 7] 번
subtask 4 의 조건을 만족하는 예제는 [예제 1], [예제 4] 번 이다.
[예제 4] 의 경우, Actor BA 의 CLIP_MODE 여부가 최종 정답에 영항을 주지 않으므로 subtask 3 검수용으로 사용할 수 있다.