[BAEKJOON][python] 백준 온라인 저지 문제 풀이 - 32069번: 가로등

문제 링크

문제
수직선 도로 위에 $N$ 개의 가로등이 켜져 있다. 각 가로등의 위치는 왼쪽부터 차례대로 $A_1 < \cdots < A_N$로 나타낼 수 있다.

위치 $x$의 어두운 정도를, 그 위치로부터 가장 가까운 가로등까지의 거리로 정의하자. 이는 $N$ 개의 수 $| A_1 - x |, \cdots, | A_N - x |$ 중에서 가장 작은 값과 같다. 여기서, $| \cdot |$는 절댓값 기호로, $y \ge 0$이면 $|y|:=y$, $y < 0$이면 $|y| := -y$이다.

예를 들어, $N = 3$ 개의 가로등이 차례대로 $A_1 = 1$, $A_2 = 4$, $A_3 = 8$에 위치한다면, $0$부터 $10$까지 각 정수 위치의 어두운 정도는 다음과 같다.

$x = 0$부터 $x = L$까지 $L+1$ 개의 정수 위치의 어두운 정도를 모두 계산했을 때, 가장 작은 값부터 $K$ 번째로 작은 값까지 차례대로 출력하는 프로그램을 작성하라.

입력
첫 줄에 세 정수 $L$, $N$, $K$가 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 $N$ 개의 정수 $A\_1, \cdots, A\_N$이 공백으로 구분되어 차례대로 주어진다.

출력
첫 줄부터 $K$ 개의 줄에 걸쳐 답을 출력한다. 이 중 $i$ 번째 줄에는 $i$ 번째로 작은 어두운 정도의 값을 출력한다.

소스코드

from collections import deque
from sys import stdin
input = stdin.readline

l, n, k = map(int, input().split())
coor = list(map(int, input().split()))

visit = set() # 이미 방문한 위치 저장
q = deque()
light = dict() # {위치: 어두운 정도}
for i in range(n):
    visit.add(coor[i])
    light[coor[i]] = 0
    q.append(coor[i])

count = 0
while q:
    i = q.popleft()
    count += 1
    if i - 1 >= 0 and i - 1 not in visit:
        light[i - 1] = light[i] + 1
        visit.add(i - 1)
        q.append(i - 1)
    if i + 1 <= l and i + 1 not in visit:
        light[i + 1] = light[i] + 1
        visit.add(i + 1)
        q.append(i + 1)
    if count == k: # k번째까지 출력할 것이기 때문에 k번 반복 후 종료
        break

light = sorted(light.items(), key=lambda x:x[1]) # 딕셔너리를 value 기준으로 오름차순 정렬
for i in range (k) :
    print(light[i][1])

정보 올림피아드 문제라서 서브태스크가 있었던 문제였습니다! 이 문제에서는 $L$ 값의 범위가 매우 크기 때문에 $L$만큼 반복하면 시간 초과가 뜹니다. 따라서 최대한 이를 피하려고 하였고, queue를 이용해 BFS 탐색을 할 때도 필요한 만큼만 연산을 수행하게 하여 최대한 소요 시간을 줄여줬습니다.

이 문제의 핵심은 BFS 방식으로 어두운 정도를 구하는 것이었습니다. 가로등이 있는 위치는 무조건 어두운 정도가 0이므로, 가로등이 있는 위치를 queue에 넣고, 해당 위치 - 1, 해당 위치 + 1의 위치의 어두운 정도를 기존 위치의 어두운 정도 + 1로 저장하면 됩니다. 한 번 방문한 위치를 다시 방문하지 않도록 visit set을 만들어서 사용하였고, 방문한 후에는 queue에 넣어 BFS 탐색을 하였습니다. $K$번째 값까지만 출력하면 되므로, 굳이 모든 위치의 어두운 정도를 구할 필요 없이 $K$번째 어두운 정도를 구하면 반복문을 빠져나와 값을 출력하도록 하였습니다.