[백준 32069] 가로등

이 문제는 2024년 정보올림피아드 2차 대회 초등부 2번, 중등부 1번, 고등부 1번으로 출제된 문제 입니다.

 

문제 출처 : https://www.acmicpc.net/problem/32069

 

가로등이 있는 위치의 어두운 정도를 0으로 하고 거리가 1씩 늘어날 때마다 어두운 정도가 1씩 늘어납니다. 이렇게 모든 위치의 어두운 정도를 구한 다음 K 번째 까지의 어두운 정도를 출력하면 됩니다.

가로등의 위치에서 1씩 멀어질 때마다 어두운 정도 1을 더해주어 각 위치의 어두운 정도를 구하면 됩니다. 이렇게 거리가 1씩 늘어날 때마다 1을 더해주는 형태의 문제는 BFS로 쉽게 해결할 수 있습니다. 하지만 문제가 BFS 형태가 아닌것 같다는 것이 문제가 됩니다. 가장 큰 문제는 숫자의 범위라 할 수 있는 L의 크기가 너무 큽니다. 다음으로 보통 BFS는 사방으로 이동이 가능한데 여기서는 앞 뒤로만 이동이 가능합니다. 이 두 가지 문제로 인해 BFS가 아닌 문제라 생각할 수 있습니다. 하나하나 문제를 해결해 나가면서 풀어보도록 하겠습니다.

문제 해결 방안

그럼 앞에서 발생한 두 가지 문제를 해결하는 방법을 생각해 보겠습니다.

앞, 뒤로만 이동하기

BFS를 인접행렬 형태로 구현할 때 상하좌우로 이동하였지만 여기서는 앞 뒤로만 이동합니다. 따라서 x값만 존재하고 y값은 없는 형태로 구현하면 쉽게 해결할 수 있습니다.

너무 큰 L의 범위

L의 값이 너무 크기 때문에 이것을 리스트로 구현할 경우 메모리 초과가 발생할 수 있습니다. 따라서 범위를 지정하는 것이 아니라 딕셔너리를 사용하여 필요한 위치를 구현하는 방식으로 문제를 해결할 수 있습니다. 딕셔너리를 잘 사용하지 않아 어떻게 사용하는지 잘 모르겠다면 아래 링크를 통해 확인 바랍니다.

https://wikidocs.net/192441

04. 딕셔너리로 만드는 성적 관리 프로그램

 

코드 작성

커다란 문제 두 가지가 해결되었으니 직접 문제를 풀어보도록 하겠습니다.

입력 받기

mii = lambda : map(int, input().split())
L, N, K = mii()
arr = mii()

x의 끝값이 되는 위치 L, 가로등의 개수 N, 어두운 정도를 출력하는 길이 K까지 세 개의 정수를 입력 받습니다. 다음으로 N개의 가로등의 위치를 입력 받아 arr에 저장합니다.

bfs 함수 구현

다음으로 bfs 함수를 구현해 보겠습니다.

from collections import deque

def bfs():
    q = deque()
    light = {}
    for a in arr:
        q.append(a)
        light[a] = 0
    
    cnt = 0
    dx = (-1, 1)
    while q:      
        x = q.popleft()
        cnt += 1
        for i in range(2):
            nx = x + dx[i]
            if 0 <= nx <= L and nx not in light:
                light[nx] = light[x] + 1
                q.append(nx)
        if cnt == K:
            break
    
    return list(light.items())

작성한 bfs 함수를 하나하나 살펴 보겠습니다. 먼저 bfs 함수의 시작 노드를 큐에 넣어야 합니다. 시작 노드는 바로 가로등의 위치가 됩니다. 따라서 반복문을 사용하여 arr의 가로등 위치를 q에 입력 합니다.

bfs 시작 노드 만들기

가로등의 값은 딕셔너리를 사용합니다. 따라서 {} 기호를 사용하여 딕셔너리로 만들어 줍니다. 그냥 리스트를 사용한다면 범위가 너무 크기 때문에 메모리 초과가 발생합니다. 만들어 준 딕셔너리의 가로등의 어두운 정도를 0으로 초기화 해주었습니다.

q = deque()
light = {}
for a in arr:
    q.append(a)
    light[a] = 0

추가적으로 bfs 함수의 필수 요소중 하나인 visited 리스트를 만들지 않았습니다. 이 것 역시 딕셔너리로 만들어도 되긴 하지만 메모리가 많이 사용될 것 같아서 visited를 만들지 않았습니다. 그럼 visited를 만들지 않고 어떻게 bfs 함수를 구현할까요? 잘 생각해보면 light를 딕셔너리로 만들었기 때문에 light 에 해당 노드가 있다면 이미 방문한 곳이고, 해당 노드가 없다면 아직 방문하지 않았다는 뜻이 됩니다. 따라서 visited 대신 light가 있는지 없는지로 방문 여부를 정할 것입니다.

bfs 초기화

기존 bfs 함수는 상하좌우를 방문 하였지만 여기서는 좌우로만 이동할 것입니다. 따라서 dx만 만들어 주었습니다. 그리고 우리는 모든 위치의 어두운 정도를 구할 필요가 없습니다. K까지의 어두운 정도를 구해주면 되기 때문에 K번째까지만 확인하기 위해 cnt 를 사용하여 cnt 값이 K와 같아지면 bfs 함수를 종료하면 됩니다.

cnt = 0
dx = (-1, 1)

while 문 시작

bfs 함수의 while문을 살펴 보겠습니다. q가 빌 때까지 반복문을 계속 진행 합니다. 큐에 있는 가장 앞에 있는 노드를 x에 저장합니다. 그리고 K번째까지만 확인할 cnt 값을 1 늘려줍니다.

 		while q:      
        x = q.popleft()
        cnt += 1

좌, 우 방문하기

이제 for 반복문을 사용하여 좌, 우를 탐색 합니다. 좌, 우만 탐색하면 되기 때문에 for문은 2번만 반복합니다. x의 다음 노드인 nx가 0과 L 사이인지 확인하고, 이미 방문했던 곳인지는 확인합니다. 아직 방문하지 않은 곳이라면 어두운 정도를 이전 값에 1을 더한 값으로 생성하고, 다음 노드를 큐에 넣어줍니다.

        for i in range(2):
            nx = x + dx[i]
            if 0 <= nx <= L and nx not in light:
                light[nx] = light[x] + 1
                q.append(nx)

K번째에 종료하기

마지막으로 cnt값이 K와 같아진다면 더 이상 확인할 필요가 없기 때문에 bfs 함수에서 빠져 나옵니다. 그리고 만들어진 light 딕셔너리를 리스트로 만들어 리턴해 줍니다. 리스트로 만드는 이유는 K번째까지 어두운 정도를 정렬하여 출력해야 하기 때문입니다. 그리고 만들어진 리스트를 리턴합니다.

        if cnt == K:
            break
    
    return list(light.items())

출력하기

위에서 만든 light 리스트를 정렬하여 K번째까지 출력하는 부분을 구현합니다.

rst = bfs()
rst.sort(key=lambda x : x[1])

for i in range(K):
    print(rst[i][1])

rst에는 bfs 함수를 통해 만들어진 light의 리스트가 들어있습니다. 이 리스트에는 (노드, 어두운 정도) 형태로 리스트가 만들어져 있습니다. 따라서 그냥 정렬을 하면 안되고 key를 사용하여 어두운 정도로 정렬해야 합니다. 그리고 K번째까지 정렬된 어두운 정도를 출력하면 됩니다.

전체 코드

전체 코드를 확인해 보겠습니다.

from collections import deque

mii = lambda : map(int, input().split())
L, N, K = mii()
arr = mii()

def bfs():
    q = deque()
    light = {}
    for a in arr:
        q.append(a)
        light[a] = 0
    
    cnt = 0
    dx = (-1, 1)
    while q:      
        x = q.popleft()
        cnt += 1
        for i in range(2):
            nx = x + dx[i]
            if 0 <= nx <= L and nx not in light:
                light[nx] = light[x] + 1
                q.append(nx)
        if cnt == K:
            break
    
    return list(light.items())

rst = bfs()
rst.sort(key=lambda x : x[1])

for i in range(K):
    print(rst[i][1])