[퀴즈] 프로그래머를 위한 문제 #3 - 미로 찾기

[퀴즈] 프로그래머를 위한 문제 #3

요즘 퀴즈를 풀다보니 재미가 들렸나, 필자가 문제를 하나 내보려고 한다. 어려울 수도, 그렇지 않을 수도 있는 문제이며, 효율적인 코드를 작성하는 것 보다 최대한 짧게 짜는 것이 목적이다.

문제의 유형과 정답의 유형은 지난 문제를 참고하면 된다.

• [퀴즈] 프로그래머를 위한 문제 #1
• [퀴즈] 프로그래머를 위한 문제 #2

미로 찾기 게임

문제는 미로 찾기 게임이다.

1. 10 x 6 (가로, 세로) 크기에 * 문자가 채워진 직사각형
2. 미로의 크기가 변해도 실행 가능해야 한다.
3. 문자 S 는 입구 위치, 문자 E는 출구 위치이다.
4. S 문자와 E 문자 사이에는 공백으로 연결된 길이 있고, 길은 여러 갈래일 수 있다.
5. 길(공백)은 2x2(가로, 세로) 이상의 공간을 가질 수 없다.
6. 미로 찾기를 시작하는 함수가 호출되기 이전의 초기화를 위한 코드는 코드 길이에서 제외된다.
7. 코드 길이는 최대한 짧게 작성한다. (알고리즘 효율성은 측정 안함)
8. 개발 언어는 무관, 언어별로 가장 짧게 작성한 코드가 우승(?)

미로 찾기 게임 예제 코드

// 아래의 변수의 초기화는 코드 길이에서 제외된다.  
map = """  
**********  
** **    E
*   * ****
* * * *  *
* *    * *
S ****   *  
**********"""

y = map.indexof("S") / maxX
x = map.indexof("S") % maxX  

// 아래 코드 부터 코드 길이를 잰다. 개행 문제는 코드 길이에서 제외  
void explore(x,y)
{
    // ...생략...
}  

정답

아래는 필자가 작성한 코드이다. 짧게 작성하는 방법은 여러 가지이므로 혹시 여러분들께서 C++ 또는 자바스크립트, C# 등으로 작성하신 코드는 댓글로 달아주세요.

Python( 파이썬 )

아래 주석의 begin code/end code 사이의 문자는 총 273 문자. 방향에 대한 가중치를 주면 훨씬 빠르게 길을 찾을 수 있지만, 여기에선 구현을 제외했다.

#123456789
m = """  
**********  
** **    E
*   * ****
* * * *  *
* *    * *
S ****   *  
**********"""

X = m.index("\n", 1) - 1
Y = m.count("\n") - 1
m = m.replace("\n", "")  

(y, x) = divmod(m.index("S"), X)  

### 총 273 바이트 ###  
########### begin code ############  
def E(x,y,a):  
 n=m[x+(y*10)]  
 if n=="*"or x<0 or x>X or y<0 or y>Y:return None

 # print "%d, %d" % (x, y)  
 if n=="E": print("END");quit()

 while a!=2 and E(x+1,y,1)!=None:pass  
 while a!=1 and E(x-1,y,2)!=None:pass  
 while a!=8 and E(x,y+1,4)!=None:pass  
 while a!=4 and E(x,y-1,8)!=None:pass  

E(x,y,0)  
############# end code ##############


## 실행 결과 ##  
0, 5  
1, 5  
1, 4  
1, 3  
1, 2  
2, 2  
3, 2  
3, 3  
3, 4  
4, 4  
5, 4  
6, 4  
6, 5  
7, 5  
8, 5  
8, 4  
8, 3  
7, 3  
5, 3  
5, 2  
5, 1  
6, 1  
7, 1  
8, 1  
9, 1  
END