지침
Smart Game Format 문자열을 파싱해요.
SGF는 보드 게임 파일, 특히 바둑 파일을 저장하는 표준 형식이에요.
SGF는 꽤 단순한 형식이에요. SGF 파일은 보통 각 노드가 속성 목록인 노드 트리 하나를 담고 있어요. 속성 목록은 키와 값의 쌍으로 이루어져 있고, 각 키는 한 번만 나올 수 있지만 값을 여러 개 가질 수 있어요.
이 연습 문제에서는 SGF 문자열을 파싱해서 속성 트리 구조를 반환하게 될 거예요.
SGF 파일은 다음과 같이 생겼어요:
(;FF[4]C[root]SZ[19];B[aa];W[ab])
이것은 노드 세 개로 이루어진 트리예요:
- 최상위 노드에는 속성이 세 개 있어요: FF[4] (키 = "FF", 값
= "4"), C[root](키 = "C", 값 = "root"), SZ[19] (키 =
"SZ", 값 = "19"). (FF는 SGF의 버전을, C는 주석을, SZ는 바둑판의 크기를 나타내요.)
- 최상위 노드에는 자식이 하나 있고, 그 자식에는 속성이 하나 있어요:
B[aa]. (흑은 "aa"로 인코딩된 지점, 즉
1-1 지점에 둬요.)
- B[aa] 노드에도 자식이 하나 있고, 그 자식에는 속성이 하나 있어요:
W[ab].
짐작하겠지만 SGF 파일에는 자식이 하나뿐인 노드가 아주 많아요. 그래서 이를 위한 축약형이 있어요.
SGF는 여러 가지 수순을 표현할 수 있어요. 바둑을 두는 사람들은 복기할 때 이 수를 두었다가 되돌리고 저 수를 두었다가 되돌리는 일을 자주 해요(이렇게 해보자, 안 되네, 저렇게 해보자). SGF는 이런 수순의 변화를 지원해요. 예를 들어:
(;FF[4](;B[aa];W[ab])(;B[dd];W[ee]))
여기서 루트 노드에는 두 가지 변화가 있어요. 첫 번째 변화(관례상 실제로 둔 수를 나타내요)는 흑이 1-1에 두는 것이에요. 흑은 스승에게 이 파일을 받았는데, 스승은 루트 노드의 두 번째 자식에 있는 더 합리적인 수를 짚어 줬어요: B[dd] (4-4 지점, 귀를 차지하는 아주 표준적인 첫 수예요).
하나의 키에 값을 여러 개 연결할 수도 있어요. 예를 들어:
(;FF[4];AB[aa][ab][ba])
여기서 AB(흑 추가)는 바둑판에 흑 돌 세 개를 추가하는 데 쓰여요.
모든 속성 값은 SGF 텍스트 타입이에요.
다른 값 타입은 구현할 필요가 없어요.
텍스트 타입의 전체 문서를 읽어볼 수도 있지만, 중요한 점만 정리하면 다음과 같아요:
-
\ 바로 뒤에 오는 줄바꿈은 제거되고, 그렇지 않은 줄바꿈은 그대로 남아요.
- 줄바꿈을 제외한 모든 공백 문자는 스페이스로 변환돼요.
-
\는 이스케이프 문자예요.
\ 뒤에 오는 공백이 아닌 문자는 그대로 삽입돼요.
\ 뒤에 오는 공백 문자는 위 규칙을 따라요.
SGF에는 \t나 \n 같은 공백 문자를 위한 이스케이프 시퀀스가 없어요.
다음 두 가지를 혼동하지 않도록 주의해요:
- 테스트에서 문자열 리터럴로 표현된 문자열
- SGF 파서에 전달되는 문자열
문자열 리터럴의 이스케이프 시퀀스는 SGF 파서에 전달되기 전에 이미 프로그래밍 언어의 파서에 의해 처리되었을 수 있어요.
SGF(그리고 일반적인 파싱)에는 더 복잡한 부분이 몇 가지 있지만, 대부분 무시해도 돼요. 입력은 UTF-8로 인코딩되어 있다고 가정해요. 테스트에는 charset 속성이 없으니 걱정하지 않아도 돼요. 게다가 모든 줄바꿈은 유닉스 스타일이라고 가정해도 돼요(테스트에는 \r이나 \r\n 없이 \n만 있어요). 속성, 노드 등 사이에 선택적으로 들어가는 공백도 테스트에는 없어요.
