2002년 가을학기 문제해결기법 - 문제 3

피라미드

지금은 BC 1000년이다. 파라오의 피라미드를 완성하였고, 내부 공사를 시작하려고 한다. 그런데, 내부 공사를 위하여 내부에 불을 밝혀야 하는 어려움이 있다. 아직은 전기가 발견되지 않아 전등을 이용할 수 없고, 또 연기와 그을음 때문에 불을 피울 수도 없다. 건축가들은 거울로 태양빛을 반사시켜서 원하는 곳을 밝히도록 제안하였다. 그래서 몇몇 개의 거울을 내부에 설치하였다. 문제는 현재 작업하고 있는 곳을 밝히도록 거울의 방향을 결정하는 것이다. 이를 위하여 현재 작업 중인 층의 2차원 지도가 입력된다. 이 지도에는 빛의 출발점, 도착점, 장애물, 거울, 그리고 현재 빛의 경로가 표시된다.

m행, n열로 표시되는 지도의 각 행은 n개의 문자로 표시된다. 지도에 나타날 수 있는 문자는 아래와 같다.

O 빛의 출발점(Origin)

D 빛의 도착점(Destination)

\ 거울, 방향 1

/ 거울, 방향 2

# 장애물

.  빈공간(아무것도 없음)

| 세로로 움직이는 빛

- 가로로 움직이는 빛

+ 교차하는 빛

빛의 출발점 O는 경계에 있고, 나머지 경계는 모두 장애물이다. 물론 장애물은 빛이 통과하지 못한다. 빛은 수직, 수평으로만 움직일 수 있으며, 거울은 빛을 정확히 90도로만 반사시킨다. 방향 1인 거울 \은 현재 북쪽에서 오는 빛을 동쪽으로, 남쪽에서 오는 빛은 서쪽으로 반사시킨다. 동쪽에서 오는 빛은 북쪽으로, 서쪽에서 오는 빛은 남쪽으로 반사시킨다. 방향 2인 거울은 방향 1인 거울과 반대 방향으로 빛을 반사시킨다.

문제는 거울이나 장애물의 위치를 옮기지 않고, 거울의 방향을 적절히 설정하여 빛이 도착점까지 도달하도록 경로를 찾는 것이다.

프로그램명은 mirror.xxx라고 하고 실행 파일명은 mirror.exe로 한다. 프로그램의 실행 시간은 3초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫 줄에 m과 n이 입력된다. m, n은 모두 100 이하인 정수이며, 이들 사이에 공백이 있다. 둘째 줄부터 m개의 줄에 2차원 지도가 한 줄에 한 행씩 입력된다. 입력되는 문자들 사이에는 공백이 없다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 입력형식과 마찬가지로 m개의 줄에 2차원 지도를 출력한다. 설치된 거울의 방향과, 출발점에서 도착점까지 빛이 움직이는 경로를 |, -, +를 이용하여 지도에 표시한다.

입력과 출력의 예 (1)

INPUT.TXT

4 6

###O##

#..|.#

#D.\-#

######

OUTPUT.TXT

###O##

#..|.#

#D-/.#

######

입력과 출력의 예 (2)

INPUT.TXT

11 49

##O##############################################

##|#............................................#

#.|............................../..\...........#

#.|.....\.......................................#

#.|..............#####..........................#

#.|......../......................../...........#

#.|..............#####..........................#

#.\------------------------------\..............#

#......###...###.................|..............#

#......###.D.###-----------------/..............#

#################################################

OUTPUT.TXT

##O##############################################

##|#............................................#

#.|............................../--\...........#

#.|.....\........................|..|...........#

#.|..............#####...........|..|...........#

#.|......../---------------------+--/...........#

#.|........|.....#####...........|..............#

#.\--------+---------------------/..............#

#......###.|.###................................#

#......###.D.###................./..............#

#################################################