안녕하세요. D번 setter ryuwonha(beingryu) 입니다.

이 문제의 비화를 전하자면, 사실 모의고사를 준비할 때 각 사람마다 쉬운 문제 하나, 어려운 문제 하나씩을 가지고 모이기로 했었습니다. 그런데 제가 들고 온 쉬운 문제가 바로 이 문제였고, 어려운 문제는 다른 문제여서 출제진에게 이게 어째서 쉬운 문제냐 ㅇ<-< 라고 구박을 들었더랬습니다 ㅠ.ㅠ 사실 두 문제 다 생각보다는 어렵지 않은 데 말이지요. fastest로 푼 Gumx 팀을 보면 더더욱 알 수 있습니다.

이 문제를 푸는 방법은 특정히 어떤 알고리즘을 요구한 것이 아니기 때문에 당연히 매우 여러 가지가 존재합니다. 여기서는 두 가지 approach 정도를 설명해 보겠습니다.



1. 탐색의 순서를 고정한 DFS (Gumx 팀 등의 풀이)
상당히 깔끔하게 구현할 수 있는 풀이입니다. 기본적인 아이디어는, 어떤 탐색되지 않은 검은 색 격자가 최초로 등장할 경우 임의로 정한 탐색 순서에 따라서(즉 Monte Carlo method처럼 탐색 순서를 매번 다르게 정하는 것이 아니라, 이를테면 상하좌우의 순서대로 방문하게 합니다. 그리고 방문하는 칸들을 두 종류로 나누는데, 각각 꼭지점과 중간점이라 칭합시다. 중간점은 그야말로 선분을 늘림으로써 생긴 의미 없는 점들이라, 이 점들을 결국엔 제거한다고 생각하면 됩니다. 그러면 이러한 중간점은,

#@#

#
@
#

위의 그림에서 @로 표시된 칸들과 같이, 다른 점들과는 연결되지 않고 좌우/상하로만 연결된 격자라고 할 수 있겠지요. 이렇지 않은 격자(=꼭지점)을 탐색하는 순서대로 각 꼭지점이 어떻게 상하좌우로 연결되어 있는지 리스트에 집어넣는다고 칩시다.

탐색 순서를 상하좌우의 순서라고 할 때, 0이라는 문자는 항상

하우 / 상우 / 상좌 / 하좌

와 같이 연결된 네 개의 꼭지점을 순서대로 탐색하게 됩니다. 길이를 얼마를 늘렸던지 간에 말이죠. 이와 같이 0-9까지의 패턴을 precode한 후 대조하여 풀면 됩니다.



2. case-by-case search

한편, 위와 같은 탐색은 일반적인 비슷한 모양 문자에 대해서 적용할 수 있는 반면 dfs로 탐색하지 않고 경우를 나누어 푸는 방법도 있을 수 있겠습니다. 예를 들어 위에서와 같이 검은 색 격자를 최초로 발견했다고 칩시다. 그렇다면 그 격자는 그 문자에 대해 가장 왼쪽 위의 격자가 됩니다.

그렇다면 그 격자에서 오른쪽으로 연결되어 있다면 그 문자는 0, 2, 3, 5, 6, 7, 8, 9 중 하나입니다. 그렇지 않다면 1, 4 중 하나입니다.

이와 같이 코드 내에서 적당한 깊이의 분기문과 기준을 삼으면 위와 같은 briliant idea 없이도 쉽게 풀 수 있습니다. 다만, 각 케이스에 대한 검증을 확실히 해야 할 것입니다.



코드는 지금 자리에 준비되지 않았네요. 다음에 준비되면 다시 업로드할게요.
이 게시물을..