[BOJ 2424] 부산의 해적

View as PDF

Submit solution

Points: 4
Time limit: 1.0s
Memory limit: 128M

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

수아는 보물 지도를 얻었다. 보물 지도는 N × M 크기이고 1 × 1크기의 정사각형으로 나누어져 있다. 보물 지도의 각 칸은 바다이거나 섬의 일부이다. 그리고, 지도에는 보물과 부산의 해적선의 위치도 있다. 마지막으로 수아는 자신의 위치를 지도에 표시했다.

자 이제, 수아는 보물을 가지기 위한 경로를 정해야 한다. 경로는 현재 수아의 위치에서 시작해야 하고, 보물의 위치에서 끝나야 한다. 매번 수아가 이동할 때, 수아는 위, 아래, 오른쪽, 왼쪽 중의 한 방향으로 이동해야 하고, 섬으로 들어가면 안 된다. 하지만, 부산의 해적도 수아와 같은 방식으로 이동할 것이므로, 부산의 해적을 조심해야 한다. 매번 수아가 이동한 후에, 해적은 수아의 이동에 대해서 이동할지 멈춰있을지 결정할 수 있다. 수아의 움직임과 해적의 반응을 턴이라고 부르면, 매 턴이 지난 후에 다음과 같이 2가지 방법으로확인할 수 있다.

  • 만약 수아가 해적과 바라보고 있다면 (해적과 수직선, 수평선상에 수아가 있고, 오직 그 사이에 바다만 있을 때) 수아는 죽는다.
  • 만약, 수아가 아직 죽지 않았고, 보물 위치에 있다면, 수아는 보물은 얻은 것이다.

부산의 해적이 어떻게 움직이건 관계없이 수아가 죽지않고 보물을 얻을 수 있는 경로를 구하는 프로그램을 작성하시오. 

입력 형식

첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에 보물 지도가 주어진다. 각 줄은 M개의 문자로 구성되어 있는데, .은 바다이고, I는 섬이고, V는 해적의 위치이고, Y는 현재 수아의 위치이고, T는 보물의 위치이다. V, Y, T는 모두 한 번씩 등장한다. (1 ≤ N, M ≤ 700)

출력 형식

첫째 줄에 수아가 보물을 얻을 수 있으면 YES를 출력하고, 그렇지 않으면 NO를 출력한다.

예제 입력 1

5 7
Y.....V
..I....
..IIIII
.......
...T...

예제 출력 1

YES

예제 입력 2

5 7
Y....V.
..I....
..IIIII
.......
...T...

예제 출력 2

NO

예제 입력 3

2 3
.YT
VII

예제 출력 3

NO

힌트

첫 번째 예제의 경우 아래 아래 아래 오른쪽 오른쪽 오른쪽 아래와 같이 움직이면 수아는 보물을 얻을 수 있다.


Comments

There are no comments at the moment.