알고리즘 스터디 - 백준 23269번 : 엘리베이터 조작 (feat. Python)

문제 해석

1. 1층부터 N층까지 사람들이 엘리베이터를 기다리고 있고
2. 각 사람 마다 가고 싶어하는 층이 존재하고 있고
3. 엘리베이터에는 1명만 탑승할 수 있다

입력

1. 건물 층 수 N
2. N개의 정수 A1~AN, 그 층에 존재하는 사람들이 가고 싶어하는 층이 나온다.

어떤 알고리즘을 써야할까??

일단 문제를 해석하기에 앞서서 알고리즘 분류별 문제에서 선정했기에 위상정렬 문제인 것은 잘 알고 있었다. 그래서 처음에는 위상정렬을 적용해 아래와 같은 코드로 작성하여 테스트케이스를 통과했다.

# if everyone arrives in destination, degree should have only zero
while elevator:
    if len(set(degree)) == 1 or len(set(visited)) == 1:
        break
    
    # get the current person and find next destination
    current_person = elevator.pop(0)
    visited[current_person] = True

    # go to destination and add the visiting place
    result.append(floor[current_person])
    degree[floor[current_person]] -= 1

    # find the next person
    next_person = floor[current_person]

    # if there is no person in that floor
    if visited[next_person]:
        # find the place you didn't visit
        # if there is no where to go, break
        for i in range(1, n+1):
            if visited[i] == False:
                elevator.append(i)
                result.append(i)
                break
        
        if len(set(degree)) == 1 or len(set(visited)) == 1:
            break
        # continue
    # if you did not visit a place, add next_person and decrease the degree
    else:
        if len(set(visited)) != 1:
            elevator.append(next_person)

근데 왠걸? 시간초과가 나타나게 되었고 자꾸 다른 부분을 수정을 해도 실패하거나 시간초과가 뜨게 되었다. 그래서 아예 다른 방식으로 생각을 하게 되었다.

DFS를 사용해 갈 수 있는 곳까지 방문

알고리즘 분류를 보니까 깊이 우선 탐색이 존재함을 알게 되어 DFS를 사용하여 결과 값에 계속 집어넣으며 수정을 거듭해서 테스트케이스를 통과하여 제출을 했다.

또 왠걸? 2%까지 가다가 틀리게 되었다. 그래서 멘붕이 왔었는데 좀 생각해보니 위상정렬로 분류로 되어 있었다는 것은 반드시 이러한 부분을 사용해야 되는 것이 아닐까 싶어서 degree가 가장 작은 노드부터 시작하는 위상정렬의 특성과 자동으로 정렬해주는 우선순위 큐 heap을 사용하였다.

Peusdo Code 작성하기

1. n, floor를 입력받기
2. 각 floor마다 가고자 하는 곳의 degree를 늘려줌
3. 1층부터 시작함으로 1층부터 깊이우선탐색을 진행
4. 방문하지 않은 층들을 찾아 elevator로 삽입해줌
5. degree가 가장 작은 것부터 트리에서 꺼내 dfs를 진행하고 결과를 출력

알고리즘 코드

Visual Studio Code에서 한글로 작성하면 자꾸 깨져가지고 귀찮아서 영어로 주석을 달아놓았다. 그리고 Python으로 작성한 글은 검색해보니 나만 있던데 조회수 잘 나오겠지??

import heapq

# get values from input
n = int(input())
floor = [0] + list(map(int, input().split()))

# result means the elevator buttons 
result = []

# for get sequence, using degree
degree = [0] * (n+1)
for i in floor:
    degree[i] += 1

# for finding the person who did not use elevator, declare visited
visited = [True] + [False] * (n)

# using dfs, find the deepest path of tree
def dfs(x):
    if visited[x]:
        return
    visited[x] = True
    result.append(floor[x])
    dfs(floor[x])

# starting point is first floor
dfs(1)

elevator = []

# by using heap, start the smallest value of degree
for i in range(1, n+1):
    if visited[i] == False:
        heapq.heappush(elevator, (degree[i], i))

while elevator:
    priority, current = heapq.heappop(elevator)

    if visited[current]: continue
    # if there is place elevator didn't visit, go to that place
    result.append(current)
    dfs(current)

# print the output
print(len(result))
print(*result)