Time Limit: 10s
Memory Limit: 128MB
으 머리야 허리야.... 간밤에 술을 겁나 먹었던거까진 기억나는데 그 이후의 기억이 없네.. 빨리 집에가서 쉬고싶....? 어라? 여긴 어디지?
그렇다! 술에 잔뜩 취해 필름이 끊겼던 나는 지금 이상한 건물에 들어와버렸다!! 빨리 집에 가서 쉬고싶은데 말이다. 여긴 어디고 나는 누구인가..
다행히도 현재 내 수중엔 이 건물의 지도와 (이런걸 왜 가지고 있지? 술마시고 슬쩍했나...) 방향을 알려주는 나침반이 있다. 그리고 자동차 경적소리가 들려오는걸 보니 밖으로 나가기만 하면 택시를 타고 무사히 귀가할 수 있을거같다. 음 다행이군...
...그래서 난 지금 어디로 움직이면 되는걸까?
아뿔사! 현재 내가 지도상의 어느 위치에 있는지를 모르겠다!
자 그럼 현재 상황을 명확하게 해보자... 일단 건물의 지도는 nxn 격자형태고, 지나갈 수 있는 block과 지나갈 수 없는 block 2가지를 나타내고있구먼. 현재 내 위치는 당근 지나갈 수 있는 block중 한군데에 있겠지?
출구는.. 음.. 대충 건물의 모서리쪽 block에 도착하면 밖으로 나갈 수 있을거같다.
이제 나는 지도상으로 동,서,남,북 4가지 방향 중 하나를 선택해서 한 칸씩 움직여서 이동을 할건데...
현재 위치를 모르는 이 상황에서 섯불리 움직였다간 괜히 더 헷갈릴 수도 있으니까 내 위치가 어디이던지 상관없이 항상 탈출할 수 있도록 미리 방향을 설정해놓고 움직이고싶다.
미리 방향을 설정해놓고 움직인다는건 머리속으로 "동동남남동 으로 움직이자!" 생각해놓고, 이대로 진행한다는 뜻이다... 만약 이동방향에 벽이 있다면 그 움직임은 넘어가고 다음 방향으로 계속 이어갈거고.. 물론 이동 도중에 출구에 도착했다면 더이상 볼것도 없이 나가서 택시를 잡을거야.
자 그럼 지도를 보고..방향을 설정해볼까나....읔; 갑자기 두통이... 내가 하고싶지만 지금 술을 마셔서 그런지 머리가 아프다... 그래서 너희들이 나대신 방향을 설정해줬으면 해. 여기 지도를 줄테니까 내가 출구로 나갈 수 있는 경우들 중에서 가장 짧은걸로 구해줄 수 있겠지?
첫째 줄에 지도의 크기를 나타내는 자연수 n (n≤8) 이 들어온다.
그 다음 n x n 격자형태로 지도정보가 들어온다. "."는 이동이 가능한 block을 나태니고 "O" (대문자 o)는 이동이 불가능한 block을 나타낸다.
항상 탈출이 가능한 지도로만 주어진다고 가정해도 좋다
길이가 가장 짧은 경로의 방향을 한 줄에 하나씩 순서대로 출력한다. 동쪽은 east, 서쪽은 west, 남족은 south, 북쪽은 north로 출력한다.
경로의 길이가 같은 경우, 사전순으로 가장 앞서는걸 출력한다. 사전순은 east , north , south , west 순이다.
4 OO.O ...O OO.. O..O
east north
번) pichulia