bright

www.acmicpc.net/problem/1697

from collections import deque 

n, k = map(int,input().split())
t = [0]*100001

def bfs():
  q = deque()
  q.append(n)

  while q:
    a = q.popleft()

    if a == k : 
      print( t[k])
      return 
    
    for b in ( a-1, a+1, a*2):
      if 0<= b < 100001 and not t[b]:
        t[b] = t[a] +1
        q.append(b)

bfs()

n부터 시작 -> 이동 가능한 칸으로 이동 -> 그 칸에서 다시 센다 

한 번 처리된 곳은 또 가지 않는다. 

생각해보면 처음 나왔을 때의 값보다 작은 값이 들어오지 않는다. 

+) 이걸 dfs 로 접근하면 무한 loop가 나온다. 

www.acmicpc.net/problem/1715

import heapq
import sys 
input = sys.stdin.readline 

n = int(input())
data = [] 
for i in range(n) : data.append(int(input()))
heapq.heapify(data)
result = 0 

while data:
  first = heapq.heappop(data)

  if len(data)<=0:   # 원소가 1개 이하일 때 
    break 
  
  second = heapq.heappop(data)
  heapq.heappush(data, first+second )
  result += first + second 

for i in data : 
  result += i 

print(result)

처음 더한 값들이 반복되어 더해지므로, 가장 작은 값부터 더해야한다. 

우선순위 큐를 이용해서 작은 값을 꺼낸다. 

www.acmicpc.net/problem/1238

import heapq
import sys
input = sys.stdin.readline 

n, m, x = map(int,input().split())
# n 명, 도로 m 개 , x 마을에서 

graph= [ [] for i in range(n+1)]
for i in range(m):
  a,b,c = map(int,input().split())
  graph[a].append((b,c))

def dij(start):
  q = []
  heapq.heappush(q, (0,start))
  dist = [1e9]*(n+1)
  dist[start] = 0 

  while q:
    d, now = heapq.heappop(q)
    if dist[now]<d : continue 
    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]]:
        dist[i[0]] = cost 
        heapq.heappush(q,(cost,i[0]))
  return dist 

result = [0]
dist_x = dij(x)
for i in range(1,n+1):
  result.append( dij(i)[x] + dist_x[i] ) 

print ( max(result) )

www.acmicpc.net/problem/18352

import heapq
import sys
input = sys.stdin.readline 


n, m, k, x = map(int,input().split())
# 도시 도로 거리 출발 도시 
graph = [ [] for _ in range(n+1) ]
for i in range(m):
  a, b= map(int, input().split())
  graph[a].append(b)

# x에서 출발, 경로가 k 인 도시 오름차순 출력 없으면 -1 

def dij(start):
  q = []
  heapq.heappush(q, (0,start))
  dist = [1e9]*(n+1)
  dist[start]=0 

  while q:
    d, now = heapq.heappop(q)
    if dist[now]<d : continue 
    
    for i in graph[now]:
      cost = d + 1
      if cost<dist[i]:
        dist[i] = cost 
        heapq.heappush(q, (cost,i))
  return dist 

result = dij(x)
answer = []

for i in range(n+1) : 
  if result[i] == k : 
    answer.append(i)

if answer == [] : print(-1)
else:
  answer.sort()
  for i in answer: print(i)

www.acmicpc.net/problem/1504

import heapq
import sys
input = sys.stdin.readline

n, e = map(int,input().split()) # 정점, 간선 

graph=[ [] for _ in range(n+1) ]
for i in range(e): 
  a,b,c = map(int,input().split())
  graph[a].append((b,c))
  graph[b].append((a,c))

v1, v2 = map(int,input().split())

def dij(start):
  q = [] 
  heapq.heappush(q,(0,start))
  dist = [1e9]*(n+1)
  dist[start]=0 

  while q:
    d, now = heapq.heappop(q)
    if dist[now] < d : continue 

    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]]:
        dist[i[0]] = cost 
        heapq.heappush(q, (cost,i[0]))
  return dist 


dist_1 = dij(1)
dist_v1 = dij(v1)
dist_v2 = dij(v2)

answer = min( dist_1[v1]+dist_v1[v2]+dist_v2[n], 
  dist_1[v2]+ dist_v2[v1]+dist_v1[n])

if answer >= 1e9 : 
  print(-1)
else : 
  print(answer)

주의사항 ) 

1. 양방향 그래프 => graph 에 추가할 때 앞 뒤로 다 해주기 

2. v1, v2 는 지나는 순서가 정해진 것은 x => 경우의 수 2개로 나누어서 더 작은 것으로 선택하기 

www.acmicpc.net/problem/1916

import heapq
import sys
input = sys.stdin.readline 

n = int(input()) # 도시 
m = int(input()) # 버스 

graph = [ [] for _ in range(n+1)]
for i in range(m):
  s,e,c = map(int,input().split())
  graph[s].append((e,c)) # 도착, 비용 

s, e = map(int,input().split()) # 출발 도착 

def dij(start):
  q = []
  dist = [1e9]*(n+1)
  heapq.heappush(q, (0,start) )
  dist[start]=0

  while q : 
    d, now = heapq.heappop(q)

    if dist[now]< d : continue 

    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]]:
        dist[i[0]] = cost 
        heapq.heappush(q, (cost,i[0]))

  return dist 

result = dij(s)
print(result[e])

기본 다익스트라 구현법 사용! 

www.acmicpc.net/problem/1753

import sys
import heapq 
input = sys.stdin.readline

V,e = map(int,input().split()) # 정점, 간선 
k = int(input()) # 시작 

graph = [ [] for _ in range(V+1)]

for i in range(e):
  u,v,w = map(int,input().split())
  graph[u].append( (v,w) ) # 이어진 곳, 거리 

# 경로 존재하지 않으면 INF 

def dij(start):
  q = []
  dist = [1e9]*(V+1)
  heapq.heappush(q, (0,k) )
  dist[start]=0
  

  while q:
    d, now = heapq.heappop(q)

    if dist[now]< d : continue # 전에 방문한 적 있으면 처리하지 않음 

    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]] :
        dist[i[0]] = cost
        heapq.heappush(q, (cost,i[0]))
  return dist 

result = dij(k)

for i in range(1,V+1):
  if result[i] == 1e9 : 
    print("INF")
  else:
    print(result[i])

정점 대문자 V 

중간에 입력 받는거 소문자 v.... 

www.acmicpc.net/problem/10942

# 시간 초과

from collections import deque

n = int(input())
data = list(map(int,input().split()))
m = int(input())

result = [1]*m 

for i in range(m):
  s,e = map(int,input().split())
  if e-s <2 : continue 
  d = deque(data[s-1:e]) 
  while len(d) > 1 :
    if d.pop() != d.popleft() : 
      result[i] = 0 

for i in range(m): print(result[i])

# 정답 ( dp ) 

www.acmicpc.net/problem/10211

t = int(input())

def max_sub():
  n = int(input())
  data = list(map(int,input().split())) 

  for i in range(1,len(data)):
    data[i] += data[i-1] if data[i-1]>0 else 0
  
  return max(data)

p = []

for i in range(t):
  p.append(max_sub())

for i in range(t):
  print(p[i])

www.acmicpc.net/problem/1890

import sys
n = int(input())

graph = [list(map(int, input().split())) for i in range(n)]

d = [ [0]*n for _ in range(n) ] 
d[0][0] = 1

for i in range(n):
  for j in range(n):
    if i == j == n-1 : break 
    a = graph[i][j]

    if i+ a < n :
      d[i+a][j] += d[i][j]
    if j+a < n : 
      d[i][j+a] += d[i][j]

print(d[n-1][n-1])

d[n-1][n-1] = 0 은 항상 만족하는 조건이다. 

만약  이중 for 문에서 n-1, n-1 인 경우를 빼지 않으면 a = 0이고 i+a<n 과 j+a<n 이 모두 True 가 되어 

더하지 않아도 되는 계산을 하게 된다. 

따라서 맨 마지막 경우를 빼는 조건을 반드시 넣어 주도록 한다.