3987 - 해결

보이저 1호

 

문제

보이저 1호는 1977년에 발사된 NASA의 태양계 무인 탐사선이다. 현재 보이저 1호는 태양권덮개 (헬리오시스)에 있다.

 

보이저 1호와 같이 오랜 기간동안 활동하는 탐사선은 경로를 항성계를 만날 때 마다 라디오 시그널 메시지를 이용해서 기록하고 있다.

 

항성계를 N * M개의 직사각형으로 나누어져 있는 N행 M열의 직사각형 그리드라고 생각해보자. 

각 칸은 행성, 블랙홀을 포함할 수 있으며, 비어있을 수도 있다. 탐사선은 인접한 네 칸(위, 아래, 오른쪽, 왼쪽)중에서 

하나를 골라서 시그널을 보낸다.

시그널은 항상 일직선으로 전파되며, 행성을 만났을 경우에는 전파되는 방향이 90도로 바뀌게 된다. 

행성은 '/'와 '\'로 표현되는 두 종류가 있으며, 반사되는 법칙은 아래 그림과 같다.

시그널이 블랙홀이 있는 칸을 만나거나 항성계를 벗어날 때 까지 계속 전파된다. 

시그널이 인접한 칸으로 이동하는데 걸리는 시간은 1초이다.

탐사선이 어느 방향으로 시그널을 보내면, 시그널이 항성계 내부에 있는 시간이 최대가 되는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 500)

다음 N개 줄에는 M개의 문자가 주어지며, '/'와 '\'는 행성을, C는 블랙홀을, '.'는 빈 칸을 나타낸다.

마지막 줄에는 탐사선이 있는 위치 PR과 PC가 주어진다. (1 ≤ PR ≤ N, 1 ≤ PC ≤ M)

 

출력

첫째 줄에 시그널을 보내는 방향을 출력한다. (U: 위, R: 오른쪽, D: 아래, L: 왼쪽)

만약, 방향이 여러 가지가 존재한다면, U, R, D, L의 순서 중 앞서는 것을 출력한다.

둘째 줄에는 가장 긴 시간을 출력한다. 만약, 시그널이 항성계 내에서 무한히 전파될 수 있다면 "Voyager"를 출력한다.

---

구현하는 문제라서 처음에는 만드는 것에 애를 먹었지만 생각 보다 어렵진 않았다.

그리고 처음에는 틀렸는데 역시나 이런 문제는 패딩을 넣어 주는 것이 좋은거 같다. 패딩이 없을 때는 틀렸는데 아닐 때는 맞았다.

import sys

N, M = map(int,sys.stdin.readline().split())

total =[]

for _ in range(N):
    sub=[]
    sub.extend(sys.stdin.readline().strip())
    total.append(sub)

PR, PC = map(int,sys.stdin.readline().split())
PR, PC = PR - 1, PC - 1
URDL = ["U","R","D","L"]
D = [(-1,0),(0,1),(1,0),(0,-1)]
max_cnt = 0

for i in range(4):
    cnt = 1
    x, y = PR, PC
    dir = i
    x += D[dir][0]
    y += D[dir][1]

    stop=0
    stop_ck = False
    while(0<=x<N and 0<=y<M):
        #print(x,y,total[x][y])
        if (x,y) == (PR,PC):
            print(stop)
            stop += 1
            if stop > 3:
                DIR = URDL[i]
                stop_ck = True
                break

        if total[x][y] == "C":
            break
        if total[x][y] == "/":
            if dir in [0,1]:
                dir = 1 - dir
            if dir in [2,3]:
                dir = 5 - dir
        if total[x][y] == "\\":
            if dir in [0,3]:
                dir = 3 - dir
            if dir in [1,2]:
                dir = 3 - dir
        cnt += 1     
        x += D[dir][0]
        y += D[dir][1]
    if stop_ck:
        break
    if max_cnt < cnt:
        max_cnt = cnt
        DIR = URDL[i]

if stop_ck:
    print(DIR)
    print("Voyager")
else:
    print(DIR)
    print(max_cnt)

이렇게 하면 정확히 틀린 이유는 모르겠지만 while 조건문에서 틀린 거 같다.

그래서 패딩을 줘서

import sys

N, M = map(int,sys.stdin.readline().split())

# 블랙홀로 둘러싸기
total = [["C"] * (M+2)]     
for _ in range(N):
    total.append(["C"] + list(sys.stdin.readline().strip()) + ["C"])
total.append(["C"] * (M+2))


PR, PC = map(int,sys.stdin.readline().split())

URDL = ["U","R","D","L"]
D = [(-1,0),(0,1),(1,0),(0,-1)]
max_cnt = 0

# 4방향 탐색
for i in range(4):
    # 처음에 무조건 움직이기 때문에 1로 시작
    cnt = 1
    x, y = PR, PC
    dir = i
    # 해당 방향으로 움직이기
    x += D[dir][0]
    y += D[dir][1]

    # 무한 루프 탐지를 위해서
    stop=0
    stop_ck = False

    # 탐색 시작
    while True:
        #print(x,y,total[x][y])
        # 자기 자신을 또 지나가는 방법은 2이상일 수가 없다 올 수 있는 방향이 4이기 때문에
        if (x,y) == (PR,PC):
            #print(stop)
            stop += 1
            if stop > 3:
                DIR = URDL[i]
                stop_ck = True
                break
        
        # 블랙홀을 만나면 스톱
        if total[x][y] == "C":
            break
        # 방향 전환을 위해서
        if total[x][y] == "/":
            if dir in [0,1]:
                dir = 1 - dir
            if dir in [2,3]:
                dir = 5 - dir
        if total[x][y] == "\\":
            if dir in [0,3]:
                dir = 3 - dir
            if dir in [1,2]:
                dir = 3 - dir
        # 다음 움직이는 것을 미리 카운트하고 좌표도 이동.
        cnt += 1
        #print(total[x][y])     
        x += D[dir][0]
        y += D[dir][1]

    # 무한 루프를 발견하면 그만.
    if stop_ck:
        break
    # 4방향중 maxcnt를 찾는다.
    if max_cnt < cnt:
        max_cnt = cnt
        DIR = URDL[i]
    #print(URDL[i],cnt)

# 무한 루프일때 출력
if stop_ck:
    print(DIR)
    print("Voyager")
# 아닐 때 출력
else:
    print(DIR)
    print(max_cnt)

다른 방법 큰 차이는 없음.

import sys

N, M = map(int,sys.stdin.readline().split())

total = [["C"] * (M+2)]     # 블랙홀로 둘러싸기
for _ in range(N):
    total.append(["C"] + list(sys.stdin.readline().strip()) + ["C"])
total.append(["C"] * (M+2))

PR, PC = map(int,sys.stdin.readline().split())
PR, PC = PR, PC
URDL = ["U","R","D","L"]
D = [(-1,0),(0,1),(1,0),(0,-1)]
max_cnt = 0

for i in range(4):
    cnt = 1
    x, y = PR, PC
    dir = i

    stop=0
    stop_ck = False
    while True:
        #print(x,y,total[x][y])
        if (x,y) == (PR,PC):
            stop += 1
            if stop > 3:
                DIR = URDL[i]
                stop_ck = True
                break
        #print(total[x][y])
        x += D[dir][0]
        y += D[dir][1]

        if total[x][y] == "C":
            break

        if total[x][y] == "/":
            if dir in [0,1]:
                dir = 1 - dir
            if dir in [2,3]:
                dir = 5 - dir
        if total[x][y] == "\\":
            if dir in [0,3]:
                dir = 3 - dir
            if dir in [1,2]:
                dir = 3 - dir
        cnt += 1     
    
    #print(URDL[i],cnt)
    if stop_ck:
        break
    if max_cnt < cnt:
        max_cnt = cnt
        DIR = URDL[i]

if stop_ck:
    print(DIR)
    print("Voyager")
else:
    print(DIR)
    print(max_cnt)