[python] 백준 3043 장난감 탱크

https://www.acmicpc.net/problem/3043

3043번: 장난감 탱크

 

문제 해결

N행 N열 크기의 나무판이므로 각 행마다 하나의 탱크가 들어가고 각 열마다 하나의 탱크가 들어가야 한다는 것은 쉽게 알 수 있다.

문제는 겹치지 않고 어떻게 순서를 정해서 이동시킬 것이며 어떤 기준으로 이동시킬 것이냐가 문제이다.

어동 시키는 방법은 간단하다. 행을 기준으로 각 탱크의 위치를 정렬시킨다. 그 다음 맨 위에 행부터 아래행으로 내려가면서 1행, 2행, 3행 . . .에 매칭시키려면 어떻게 움직여야 하는지 생각한다.

위로 이동시켜야 하는 것은 up이란 리스트 안에 넣고 아래로 이동시켜야 하는 것은 down이라는 리스트에 넣는다.

그리고 up 리스트 안에 가장 위에 있는 행 탱크부터 위로 이동시킨다.

그 다음 down 리스트 안에 가장 아래에 있는 행 탱크부터 아래로 이동시킨다.

그러면 절대 겹치지 않고 이동시킬 수 있다.

열도 마찬가지이다.

가장 왼쪽 열에 있는 탱크부터 가장 오른쪽에 있는 열가지 순서대로 매칭시킬려고 한다.

왼쪽으로 이동시켜야 하는 것은 left란 리스트 안에 넣고 오른쪽으로 이동시켜야 하는 것은 right라는 리스트 안에 넣는다.

그리고 left 리스트 안에 가장 왼쪽에 있는 열 탱크부터 왼쪽으로 이동시킨다.

그 다음 right 리스트 안에 가장 오른쪽에 있는 열 탱크부터 오른쪽으로 이동시킨다.

그러면 겹치지 않고 잘 이동시킬 수 있다.

 

CODE

def updown():
    up = []
    down = []
    for i in range(1,n+1):
        if r_first[i-1][1][0] > i:
            up.append(i)
        if r_first[i-1][1][0] < i:
            down.append(i)
    for i in range(len(up)):
        for j in range(up[i],r_first[up[i]-1][1][0]):
            result.append((r_first[up[i]-1][0], 'U'))
    down = sorted(down, reverse=True)
    for i in range(len(down)):
        for j in range(r_first[down[i]-1][1][0], down[i]):
            result.append((r_first[down[i]-1][0], 'D'))

def leftright():
    left = []
    right = []
    for i in range(1,n+1):
        if c_first[i-1][1][0] > i:
            left.append(i)
        if c_first[i-1][1][0] < i:
            right.append(i)
    for i in range(len(left)):
        for j in range(left[i], c_first[left[i]-1][1][0]):
            result.append((c_first[left[i]-1][0], 'L'))
    right = sorted(right, reverse=True)
    for i in range(len(right)):
        for j in range(c_first[right[i]-1][1][0], right[i]):
            result.append((c_first[right[i]-1][0], 'R'))

if __name__=='__main__':
    n = int(input())
    r_first = []
    c_first = []
    result = []
    for i in range(1,n+1):
        r, c= map(int, input().split())
        r_first.append((i,(r,c)))
        c_first.append((i,(c,r)))
    r_first = sorted(r_first, key=lambda x: x[1])
    c_first = sorted(c_first, key=lambda x: x[1])
    updown()
    leftright()
    print(len(result))
    for i in range(len(result)):
        print(result[i][0], result[i][1], sep=' ')