[BOJ/백준] 2873 롤러코스터

import sys
def find_index(origin):
    global N,M
    min_value = 10001
    min_index = []
    for x in range(N):
        for y in range(M):
            if (x+y)%2:
                if min_value > origin[x][y]:
                    min_value = origin[x][y]
                    min_index = [x,y]
    return min_index

N,M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
if not N%2 and not M%2:
    low_index = find_index(arr)
    result = ''
    front_result = ''
    tail_result = ''
    front_times = low_index[0]//2
    tail_times = (N-1 -low_index[0])//2
    for ind in range(1,M*front_times*2+1):
        a = ind//M
        b = ind%M
        if not b:
            front_result += 'D'
        else:
            if a%2:
                front_result += 'L'
            else:
                front_result += 'R'
    for ind in range(1,M*tail_times*2):
        a = ind//M
        b = ind%M
        if not b:
            tail_result += 'D'
        else:
            if a%2:
                tail_result += 'R'
            else:
                tail_result += 'L'
    if tail_times:
        tail_result = 'D'+tail_result
    front_index = [front_times*2,0]
    move = ['D','R','U','R']
    front_direction = [(1,0),(0,1),(-1,0),(0,1)]
    tail_direction = [(-1,0),(0,-1),(1,0),(0,-1)]
    tail_index = [front_index[0]+1,M-1]
    front_cnt = 0
    tail_cnt = 0
    while True:
        nx = front_index[0] + front_direction[front_cnt][0]
        ny = front_index[1] + front_direction[front_cnt][1]
        if nx == low_index[0] and ny == low_index[1]:
            break
        else:
            front_result += move[front_cnt]
        front_cnt = (front_cnt+1)%4
        front_index = [nx,ny]
    if tail_index[0] != front_index[0] or tail_index[1] != front_index[1]:
        while True:
            nx = tail_index[0] + tail_direction[tail_cnt][0]
            ny = tail_index[1] + tail_direction[tail_cnt][1]
            if nx == front_index[0] and ny == front_index[1]:
                tail_result = move[tail_cnt] + tail_result
                break
            else:
                tail_result = move[tail_cnt] + tail_result
            tail_cnt = (tail_cnt+1)%4
            tail_index = [nx,ny]

    result = front_result + tail_result

else:
    if N%2:
        result = ''
        for ind in range(1,N*M):
            a = ind//M
            b = ind%M
            if not b:
                result += 'D'
            else:
                if a%2:
                    result += 'L'
                else:
                    result += 'R'
    else:
        result = ''
        for ind in range(1,N*M):
            a = ind//N
            b = ind%N
            if not b:
                result += 'R'
            else:
                if a%2:
                    result += 'U'
                else:
                    result += 'D'   
print(result)

 처음 풀었던 방식이다. 이 문제는 먼저 크게 3가지 경우로 나뉠 수 있다.

 

1 ) 행과 열이 전부 짝수 일때

2 ) 행과 열 중 하나라도 홀수 일때

   2.1) 행이 짝수 일때

 

 

먼저 구현하기 쉬운 2번 케이스 부터 하면, 행과 열중 하나라도 홀수이면, 모든 칸을 지나갈수 있다.

그래서 모든 칸을 지나가도록 설정을 해주면 된다.

나는 먼저 기본적으로 

 

----------->

              ↓

<-----------

이런 식으로 스네이크 방식대로 간다고 해줬다, 몇번 인덱스에서 화전하는지만 주의해서 그때의 방향에 맞게 회전을 해주면 된다.

 

하지만 이 방법은 행이 짝수이고 열이 홀수 일때는 하지 못한다.

행이 짝수이고 열이 홀수 일때는, 

 

↓  ↑

↓  ↑

↓  ↑

↓→↑

 

상하로 지그재그인 방식대로 해주었다.

 

 

그리고 어려운 행과 열이 둘다 짝수 일때이다.

 

행과 열이 전부 짝수이면, 모든 칸은 들릴수 없고, 단 1칸만 들리지 못한다.

그 칸은 주어진 행렬을 체스판 위에 있다고 하면 처음 시작 위치인 (0,0)을 흰색칸이라고 한다면, 검정색 칸 1칸을 들리지 못한다.

 

그렇기 때문에 검은색 칸 중에서 가장 값이 작은 것을 찾아 그 칸을 들릴지 않고 나머지칸을 전부 도는 것이 베스트이다.

 

들릴지 않을 칸을 구했으면, 다음과 같이 구한다. 지그재그 방식으로 갈때 보면, 행이 2칸을 기준으로 원위치로 열의 위치가 동일하게 올 수 있고, 계속 반복되는 것을 알 수 있다.

 

그렇기 때문에 주어진 행렬을 처음부터 2칸씩 나눈다고 생각을 하고, 들리지 않는 칸이 있는 2칸짜리 행을 제외한 나머지는 위에서 했던 좌우 지그재그 방식으로 반복문을 해준다.

그리고 마지막 남은 2칸은 앞뒤로 check를 해주면서 하면 된다.

 

 그려보면 알지만 D->R->U->R 순으로 반복해서 움직여준다. 

단 들리지않는 칸을 만났을시에는 그 칸을 피해서 R로 움직여주면 된다.

 

나는 위에서 내려올때, 끝에서 역으로 올라오는 것을 따로 구해서 합쳐주는 방식으로 했다.

주의 할점은 출력에 표시되는 방향은 똑같지만 꼬리부분에서 올라가는 것은 거슬러 가는것이기 때문에 실질적인 방향이 반대인것만 주의 하면 된다.

 

import sys
def find_index(origin):
    global N,M
    min_value = 10001
    min_index = []
    for x in range(N):
        for y in range(M):
            if (x+y)%2:
                if min_value > origin[x][y]:
                    min_value = origin[x][y]
                    min_index = [x,y]
    return min_index
N,M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
if not N%2 and not M%2:
    low_index = find_index(arr)
    result = ''
    front_times = low_index[0]//2
    tail_times = (N-1 -low_index[0])//2
    front_result = ('R'*(M-1)+'D'+'L'*(M-1)+'D')*front_times
    tail_result = ('D'+'L'*(M-1)+'D'+'R'*(M-1))*tail_times

    front_index = [front_times*2,0]
    move = ['D','R','U','R']
    front_direction = [(1,0),(0,1),(-1,0),(0,1)]
    tail_direction = [(-1,0),(0,-1),(1,0),(0,-1)]
    tail_index = [front_index[0]+1,M-1]
    front_cnt = 0
    tail_cnt = 0
    while True:
        nx = front_index[0] + front_direction[front_cnt][0]
        ny = front_index[1] + front_direction[front_cnt][1]
        if nx == low_index[0] and ny == low_index[1]:
            break
        else:
            front_result += move[front_cnt]
        front_cnt = (front_cnt+1)%4
        front_index = [nx,ny]
    if tail_index[0] != front_index[0] or tail_index[1] != front_index[1]:
        while True:
            nx = tail_index[0] + tail_direction[tail_cnt][0]
            ny = tail_index[1] + tail_direction[tail_cnt][1]
            if nx == front_index[0] and ny == front_index[1]:
                tail_result = move[tail_cnt] + tail_result
                break
            else:
                tail_result = move[tail_cnt] + tail_result
            tail_cnt = (tail_cnt+1)%4
            tail_index = [nx,ny]

    result = front_result + tail_result

else:
    if N%2:
        result = ('R'*(M-1)+'D'+'L'*(M-1)+'D')*(N//2)+('R'*(M-1))
    else:
        result = ('D'*(N-1)+'R'+'U'*(N-1)+'R')*(M//2) +('D'*(N-1))
print(result)

 

이 문제를 풀다보면 알지만, 굳이 모든 칸을 하나하나 탐색하면서, 반복문을 돌릴필요가 없다. 위에서 말했다 시피 2칸 단위로  지그재그로 이루어져있기때문에 2칸을 기준으로 좌우지그재그를 출력해주면된다.

 

위 코드가 그러한 방식을 이용한 것이다.

행과 열 중 홀수 일때는 모든 칸을 들릴수있고, 그 방법이 패턴화되어있기 때문에, 곱하기를 해주면 된다.

그리고 행과 열 둘다 짝수 일때에도, 2칸단위는 전부 그냥 곱하기를 해주고, 마지막 부분만 탐색을 해주면된다.