[백준_18513] 샘터 python

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

18513번: 샘터

문제해결

샘터를 기준으로 삼아 -1, +1 로 이동하는 bfs 탐색을 해주고 k채의 집이 지어졌을 때 불행도의 값을 리턴한다.

이 문제는 단순한 bfs문제임을 유추하는데엔 큰 어려움이 없었지만 //==(1)==// 아래코드부분을   

//==(2)==// 에 위치시켰을 때 메모리초과가 나는 문제였다. (우연히지만 틀려서 정말 다행이었다.)

이 문제 또한 창을 켜놓고 살면서 며칠에 걸쳐 고민했는데 너비우선 탐색은 우선 que에 들어온것에대한 작업이 끝나야

다음작업으로 들어간다. 근데 그 다음 절차(popleft가 되는부분)에서 검증(if문으로 return하는 조건설정)을 하던 습관때문에

k=0이 되는 부분을 넘어가버리기 때문에 메모리와 시간이 계속해서 쌓이는 것이었다.

k갯수를 맞추기위해 +를하거나 혹은 k가 0이될때까지 -를 하면 값이 변하는 그 순간일때 본인이 찾고싶은 값에대해 검증이 들어가야 한다.

 

이 부분만 잘 넘기면(조건을 아래에 설정했으면 이런 에러를 안접할수도.) 로직이 크게 어렵진 않은 단순 탐색문제이다.

 

from collections import deque
import sys


def input():
    return sys.stdin.readline().rstrip()


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

dic = dict()
answer = 0
que = deque()
for i in water:
    que.append(i)
    dic[i] = 1


def bfs():
    global answer, k
    while que:
        dx = que.popleft()
        #//==== (2) ====//
        for nx in [dx - 1, dx + 1]:
            if nx not in dic:
                dic[nx] = dic[dx] + 1
                k -= 1
                answer += dic[nx] - 1
                que.append(nx)

                #//=== (1)====//
                print("nx,",nx)
                if k == 0:
                    print(answer)
                    exit(0)

bfs()