[알고리즘]백준18513 샘터 - 파이썬

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

18513번: 샘터

 

 

[풀이 코드]

from collections import deque
from sys import stdin
input = stdin.readline
q = deque()
visited = dict()

N, K = map(int, input().split())
water = list((map(int, input().split())))

for w in water:
    q.append(w)
    visited[w] = 0

while q:
    if K <= 0:
        break
    x = q.popleft()
    for xx in [x-1, x+1]:
        if xx not in visited and K > 0: #방문하지 않았다면
            visited[xx] = visited[x] + 1
            K -= 1
            q.append(xx)

result = 0
for k, v in visited.items():
    result += v
print(result)

• 방문처리를 해주기 위해서 dict을 활용했다. -1, +1을 이동하면서 이동한 위치가 dict에 없다면 방문하고 직전에 있던 위치에 +1을 하여 dict값을 경신했다. 
  
  
• 조건문으로 방문처리를 할 때 K(집의 개수) 또한 생각해줘야 한다. 큐에 넣는다면 K도 1을 빼주는데 집이 한 개인 경우에도 큐에 두 개가 들어가고 K도 두 번 빼준다. 이 경우를 대비해서 K>0인 경우도 추가했다. 밑에 추가 예제 입력 넣어보면 된다.

'''
추가예제입력 : 방문처리와 k가 0이상인 경우에 큐에 추가해줘야 한다.
1 1
0
'''