Patkice

면접 대비

시간 제한1초메모리 제한512 MB

요약

한 방향 화살표로 채워진 격자에서 'o'에서 출발해 'x'에 가장 적은 걸음으로 도착하는 시작 방향을 찾고, 같으면 알파벳 순으로 고른다.

난이도: 보통10점 중 5점
유형: 그래프, 시뮬레이션, 구현, 배열
정답자: 아직 제출이 없습니다

문제

얼마 전 먼 열대 섬나라에 고무 오리 세 마리가 살고 있었다. 어느 더운 여름날 해변에 누워 있던 오리들은 근처 섬으로 여행을 떠나기로 했다. 모험을 좋아하는 오리들은 낡은 검은 우산을 타고 해류를 따라 이동하기로 했다.

오리들은 노련한 바다 탐험가라서 여행을 떠나기 전에 해류 지도를 살펴본다. 지도에서 오리들이 사는 섬은 'o'로 표시된다. 오리들은 북쪽 N, 동쪽 E, 서쪽 W, 남쪽 S 네 방향 중 어느 방향으로든 여행을 시작할 수 있다.

이 바다의 해류는 네 방향 중 하나로 흐르며 지도에 다음과 같이 표시된다. 서쪽에서 동쪽으로 흐르면 '<', 동쪽에서 서쪽으로 흐르면 '>', 북쪽에서 남쪽으로 흐르면 'v', 남쪽에서 북쪽으로 흐르면 '^'이다. 오리들이 해류가 있는 칸에 있으면 해류의 방향으로 한 칸 이동한다. 이 바다의 해류는 특별해서 지도 밖으로 나가는 일이 없고, 소용돌이(오리들이 해류를 따라가면 빙글빙글 도는 곳)를 이루지도 않는다.

잔잔한 바다는 점 '.'으로 표시된다. 해류가 오리들을 잔잔한 바다 칸이나 출발한 섬으로 데려가면 여행을 계속할 수 없다. 오리들이 가고 싶어 하는 섬은 'x'로 표시된다.

오리들은 해변 파티를 멈추고 싶지 않다. 오리들은 다른 섬에 갈 수 있는지, 갈 수 있다면 어느 방향으로 여행을 시작해야 하는지 알려 달라고 정중히 부탁한다. 오리 한 마리가 배멀미를 심하게 하기 때문에, 여행이 최대한 짧아지는 방향을 골라 달라고 한다. 같은 최소 이동 시간을 주는 방향이 여러 개라면 사전순으로 가장 앞서는 방향을 골라야 한다.

입력

첫째 줄에 지도의 행 수와 열 수를 나타내는 정수 r, s가 주어진다. (3 ≤ r, s ≤ 100)

다음 r개 줄에는 해류 지도를 나타내는 'o<>v^.x' 집합의 문자가 s개씩 주어진다. 지도에는 'o'와 'x'가 각각 정확히 하나씩 있다. 'o'는 첫째 줄이나 마지막 줄, 첫째 열이나 마지막 열에 위치하지 않는다.

출력

오리들이 다른 섬에 도달할 수 없으면 :( 를 출력한다.

그렇지 않으면 첫째 줄에 :) 를 출력한다. 둘째 줄에는 시작 방향을 출력한다. (N은 북쪽, E는 동쪽, W는 서쪽, S는 남쪽)

힌트

첫 번째 예제에서 오리들이 동쪽이 아닌 방향으로 여행을 시작하면 잔잔한 바다에 이르러 다른 섬에 도달하지 못한다.

두 번째 예제에서 오리들은 북쪽이나 남쪽으로 시작하면 다른 섬에 도달한다. 남쪽 경로가 더 짧기 때문에 남쪽을 고른다.

예제3

예제 1

입력

6 6
..>>>v
.o^..v
.v.<.v
.>>^.v
.x<<<<
......

예상 출력

:)
E

예제 2
입력
```
5 5
v<<<<
>v.>^
v<.o.
>>v>v
..>>x
```
예상 출력
```
:)
S
```
예제 3
입력
```
3 3
x>.
.o^
^<.
```
예상 출력
```
:(
```