[Python] 루돌프의 반란: 삼성SW역량테스트 2023 하반기 오후 1번

루돌프의 반란: 삼성SW역량테스트 2023 하반기, 오후 1번

 

해설/힌트 없이 채점 테스트 케이스만 보고 3시간 30분 걸렸다.

진짜 시뮬레이션 구현이 복잡했다

특히 산타끼리의 '상호작용'을 for-loop으로 구했다가 while로 고쳤다

 

오답이 나는 케이스

1. 루돌프가 움직일 때

• 산타를 찾아가는 우선순위가 제대로 되어있는가?
• 산타와 충돌했을 때, 산타가 밀리는 방향이 바뀌진 않았는가? (바뀌면 안된다)

2. 산타(들)가 움직일 때

• 상우하좌 순서를 지켰는가?
• 루돌프와 가까워지지 않으면 정지하는가?
• 루돌프와 충돌 후 다른 산타들과 '상호작용'이 제대로 구현이 되었는가?
• 루돌프와 충돌 후 제자리로 돌아올 때에도 상호작용을 하고 있는가? (하면 안된다)
• 상호작용이 끝난 후, 올바르게 위치가 업데이트 되었는가? (덮어쓰기 순서 조심)

3. 기타 구현 사항

• 산타가 탈락했을 때, 지도에서 지웠는가?
• 산타의 기절상태는 2가지이다. 새로운 턴이 될 때 기절상태를 업데이트한다.

전역변수 설계

개인적으로 프로젝트에서 전역변수를 사용하지 않는다.

그러나 코딩테스트 한정으로 전역변수를 즐겨 쓴다.

산타의 상호작용으로 인한 위치 업데이트 때문에 지도를 표현하는 2차원 배열이 필요할 것 같았다. (board)

그리고 산타는 1~P로 한정되므로 루돌프를 -1로 정의했다.

또한 산타의 상태는 4가지이고, 이를 나타낼 배열도 필요했다.

 

가급적 문제에서 설명해주는 값을 바꾸고 싶지 않아서, 2차원 배열도 (N, N)이 아니라 (N + 1, N + 1)크기로 만들었다.

N, M, P, C, D = map(int, input().split())

STATUS_READY = 0
STATUS_STUN1 = 1
STATUS_STUN2 = 2
STATUS_OUT = 3
RUDOLPH = -1

board = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
santa_status = [STATUS_READY] * (P + 1)
santa_x = [0] * (P + 1)
santa_y = [0] * (P + 1)
santa_score = [0] * (P + 1)

 

지도에서 벗어나는지 범위확인 함수, 거리를 계산하는 함수, 디버깅용 함수도 작성했다

def get_status(status_id):
    if status_id == STATUS_READY:
        return 'READY'
    elif status_id == STATUS_STUN1:
        return 'STUN1'
    elif status_id == STATUS_STUN2:
        return 'STUN2'
    else:
        return 'OUT'

def check(x, y):
    if x < 1 or x > N or y < 1 or y > N:
        return False
    return True

def distance(x1, y1, x2, y2):
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
    

def show():
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            print(board[i][j], end=' ')
        print()
    print()

산타 충돌 상호작용 코드

이부분을 구현하기 너무 어려웠다. (그리고 귀찮음)

시작점에서부터 특정 방향으로 계속 전진하여 상호작용이 끝나는 산타들의 위치를 찾는다.

이때 시작점과 끝점의 좌표를 각각 (x, y), (end_x, end_y)라 하자.

 

(end_x, end_y)에서부터 한칸씩 산타들을 옮긴다. 이때 (end_x, end_y)가 새로운 산타의 좌표가 된다.

(pre_x, pre_y)는 원래 산타위치이다.

만약 새로운 산타의 좌표(end_x, end_y)가 지도를 벗어나면 그 산타는 탈락시킨다. 

탈락되지 않는다면, 그대로 한칸씩 당겨서 옮겨주면된다.

def santa_collision(dx, dy, direction, x, y):
    end_x, end_y = x, y
    while check(end_x, end_y) and board[end_x][end_y] > 0:
        end_x += dx[direction]
        end_y += dy[direction]

    while (end_x, end_y) != (x, y):
        pre_x = end_x - dx[direction]
        pre_y = end_y - dy[direction]
        santa_id = board[pre_x][pre_y]
        if not check(end_x, end_y):
            santa_status[santa_id] = STATUS_OUT
        else:
            board[end_x][end_y] = board[pre_x][pre_y]
            santa_x[santa_id] = end_x
            santa_y[santa_id] = end_y
        end_x, end_y = pre_x, pre_y
    #print(x, y, end_x, end_y)

 

main 흐름

# 입력단계
N, M, P, C, D = map(int, input().split())
Rx, Ry = map(int, input().split())
board[Rx][Ry] = RUDOLPH
for _ in range(P):
    santa_id, r, c = map(int, input().split())
    santa_x[santa_id] = r
    santa_y[santa_id] = c
    board[r][c] = santa_id

# 시뮬레이션 시작
for t in range(M):
    num_out = 0
    for p in range(1, P + 1):
        if santa_status[p] in [STATUS_STUN1, STATUS_STUN2]:
            santa_status[p] -= 1
        if santa_status[p] == STATUS_OUT:
            num_out += 1
            
    # 모든 산타가 탈락하면 프로그램 종료
    if num_out == P:
        break
        
    # 1. 루돌프 이동 단계
    # 1.1 루돌프와 가장 가까운 산타를 찾는다.
    target_santa_id = find_closest_santa_id(Rx, Ry)
    if target_santa_id == -1:
        break

    # 1.2 루돌프를 가장 가까운 산타를 향해 한칸 이동한다
    Rx, Ry = move_rudolph(Rx, Ry, santa_x[target_santa_id], santa_y[target_santa_id])

    # 2. 루돌프 위치에 따른 모든 산타 이동
    move_stantas(Rx, Ry)

    # 탈락하지 않은 산타들은 점수를 얻는다
    for p in range(1, P + 1):
        if santa_status[p] != STATUS_OUT:
            santa_score[p] += 1

# 모든 시뮬레이션이 끝나고, 산타들의 점수를 출력한다
for p in range(1, P + 1):
    print(santa_score[p], end=' ')

Python Code

디버깅용 주석이 포함된 지저분한 코드이다.

N, M, P, C, D = map(int, input().split())

STATUS_READY = 0
STATUS_STUN1 = 1
STATUS_STUN2 = 2
STATUS_OUT = 3
RUDOLPH = -1

board = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
santa_status = [STATUS_READY] * (P + 1)
santa_x = [0] * (P + 1)
santa_y = [0] * (P + 1)
santa_score = [0] * (P + 1)

def get_status(status_id):
    if status_id == STATUS_READY:
        return 'READY'
    elif status_id == STATUS_STUN1:
        return 'STUN1'
    elif status_id == STATUS_STUN2:
        return 'STUN2'
    else:
        return 'OUT'

def check(x, y):
    if x < 1 or x > N or y < 1 or y > N:
        return False
    return True

def distance(x1, y1, x2, y2):
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)

def move_santa(p, x, y, nx, ny):
    if not check(nx, ny):
        board[x][y] = 0
        santa_x[p] = -1
        santa_y[p] = -1
        santa_status[p] = STATUS_OUT
    else:
        santa_x[p] = nx
        santa_y[p] = ny
        board[x][y] = 0
        board[nx][ny] = p

def find_closest_santa_id(rx, ry):
    santa_list = []
    for p in range(1, P + 1):
        if santa_status[p] != STATUS_OUT:
            sx, sy = santa_x[p], santa_y[p]
            dist = distance(sx, sy, rx, ry)
            santa_list.append((dist, -sx, -sy, p))
    if santa_list:
        santa_list.sort()
        return santa_list[0][-1]
    else:
        return -1

def santa_collision(dx, dy, direction, x, y):
    end_x, end_y = x, y
    while check(end_x, end_y) and board[end_x][end_y] > 0:
        end_x += dx[direction]
        end_y += dy[direction]

    while (end_x, end_y) != (x, y):
        pre_x = end_x - dx[direction]
        pre_y = end_y - dy[direction]
        santa_id = board[pre_x][pre_y]
        if not check(end_x, end_y):
            santa_status[santa_id] = STATUS_OUT
        else:
            board[end_x][end_y] = board[pre_x][pre_y]
            santa_x[santa_id] = end_x
            santa_y[santa_id] = end_y
        end_x, end_y = pre_x, pre_y
    #print(x, y, end_x, end_y)
    

def move_rudolph(x, y, tx, ty):
    dx = [-1, -1, 0, 1, 1, 1, 0, -1]
    dy = [0, 1, 1, 1, 0, -1, -1, -1]

    min_dist = float('inf')
    min_dir = -1

    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if not check(nx, ny):
            continue
        dist = distance(nx, ny, tx, ty)
        if dist < min_dist:
            min_dist = dist
            min_dir = i

    nx = x + dx[min_dir]
    ny = y + dy[min_dir]

    # check santa collision
    if board[nx][ny] > 0:
        p = board[nx][ny]
        santa_score[p] += C
        #new_dir = (min_dir + 4) % 8
        nsx = nx + C * dx[min_dir]
        nsy = ny + C * dy[min_dir]
        #print(nx, ny, min_dir, '*', nsx, nsy)

        # new santa's position is not valid
        if not check(nsx, nsy):
            santa_status[p] = STATUS_OUT
            santa_x[p] = -1
            santa_y[p] = -1
            board[x][y] = 0
            board[nx][ny] = RUDOLPH
            return nx, ny

        # chain collisions
        if board[nsx][nsy] > 0:
            santa_collision(dx, dy, min_dir, nsx, nsy)
        board[nx][ny] = 0
        board[nsx][nsy] = p
        santa_x[p] = nsx
        santa_y[p] = nsy
        santa_status[p] = STATUS_STUN2


    board[x][y] = 0
    board[nx][ny] = RUDOLPH
    return nx, ny

def move_stantas(rx, ry):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    for p in range(1, P + 1):
        if santa_status[p] == STATUS_READY:
            min_dist = float('inf')
            min_dir = -1
            sx, sy = santa_x[p], santa_y[p]
            min_dist = distance(sx, sy, rx, ry)
            for i in range(4):
                nx = sx + dx[i]
                ny = sy + dy[i]
                if not check(nx, ny):
                    continue
                if board[nx][ny] > 0:
                    continue
                dist = distance(nx, ny, rx, ry)
                if dist < min_dist:
                    min_dist = dist
                    min_dir = i
            if min_dir == -1:
                continue

            nsx = sx + dx[min_dir]
            nsy = sy + dy[min_dir]
            if board[nsx][nsy] == 0:
                move_santa(p, sx, sy, nsx, nsy)
            elif board[nsx][nsy] == RUDOLPH:
                santa_score[p] += D
                new_dir = (min_dir + 2) % 4
                nsx = nsx + D * dx[new_dir]
                nsy = nsy + D * dy[new_dir]

                if not check(nsx, nsy):
                    santa_status[p] = STATUS_OUT
                    board[sx][sy] = 0
                    santa_x[p], santa_y[p] = -1, -1
                else:
                    if board[nsx][nsy] > 0 and board[nsx][nsy] != p:
                        # chain collisions
                        santa_collision(dx, dy, new_dir, nsx, nsy)
                    board[sx][sy] = 0
                    board[nsx][nsy] = p
                    
                    santa_x[p], santa_y[p] = nsx, nsy
                    santa_status[p] = STATUS_STUN2

def show():
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            print(board[i][j], end=' ')
        print()
    print()

Rx, Ry = map(int, input().split())
board[Rx][Ry] = RUDOLPH
for _ in range(P):
    santa_id, r, c = map(int, input().split())
    santa_x[santa_id] = r
    santa_y[santa_id] = c
    board[r][c] = santa_id

for t in range(M):
    #print('turn:', t + 1)
    num_out = 0
    for p in range(1, P + 1):
        if santa_status[p] in [STATUS_STUN1, STATUS_STUN2]:
            santa_status[p] -= 1
        if santa_status[p] == STATUS_OUT:
            num_out += 1

    if num_out == P:
        break
    # move rudolph
    target_santa_id = find_closest_santa_id(Rx, Ry)
    if target_santa_id == -1:
        break

    #print('target_santa', target_santa_id)
    Rx, Ry = move_rudolph(Rx, Ry, santa_x[target_santa_id], santa_y[target_santa_id])
    #print('R', Rx, Ry)

    # move santas
    move_stantas(Rx, Ry)

    # gain score for survival stantas
    for p in range(1, P + 1):
        if santa_status[p] != STATUS_OUT:
            santa_score[p] += 1
        #print(p, santa_x[p], santa_y[p], get_status(santa_status[p]), santa_score[p])
    #show()

    # move santa
for p in range(1, P + 1):
    print(santa_score[p], end=' ')