bright

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 가 되어 

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

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

www.acmicpc.net/problem/1743

from collections import deque

n, m , k = map(int,input().split()) # 세로 가로 음식물 수 
graph = [ [0]*m for i in range(n)]
for i in range(k):
  a,b = map(int,input().split())
  graph[a-1][b-1] = 1 


dx = [-1,1,0,0]
dy = [0,0,1,-1]

def bfs(x,y):
  q = deque()
  q.append((x,y))
  graph[x][y] = 0 
  cnt = 1 

  while q : 
    a, b= q.popleft()
    for i in range(4):
      nx = a + dx[i]
      ny = b + dy[i]

      if nx<0 or nx>=n or ny<0 or ny>=m : 
        continue 
      if graph[nx][ny] == 1:
        cnt += 1 
        q.append((nx,ny))
        graph[nx][ny] = 0 
  return cnt 

tmp = 0 

for i in range(n):
  for j in range(m):
    if graph[i][j] != 0 :
      tmp = max(tmp, bfs(i,j))

print(tmp)

programmers.co.kr/learn/courses/30/lessons/43162

def dfs(graph, v, visited) : 
    tmp = 0 
    if not visited[v] :
        visited[v] = True
        for i in range( len(graph[v]) ):
            if graph[v][i] :
                dfs(graph, i, visited)
                tmp += 1 
        
        if tmp >= 1 : return True
    return False

def solution(n, computers):

    visited = [False] * n
    answer = 0

    for i in range(n):
        if dfs(computers, i , visited): 
            answer += 1 
    return answer

=> 조금 더 간결하게 

def dfs(graph,v, visited):
    
    if visited[v] == 1 : 
        return False 
    
    visited[v]=1
    for i in range(len(graph[v])):
        if graph[v][i]==1 :
          dfs(graph,i,visited)
    return True
    

def solution(n, computers):
    
    answer = 0 
    visited= [0]*n
    
    for i in range(n):
        if dfs(computers,i,visited) == True : 
            answer += 1 

    return answer

programmers.co.kr/learn/courses/30/lessons/43165

def solution(numbers, target):
    sup= [0]
    for i in numbers:
        sub = []
        for j in sup : 
            sub.append(j+i)
            sub.append(j-i)
        sup = sub
    return sup.count(target)

programmers.co.kr/learn/courses/30/lessons/64061

def solution(board, moves):
    
    doll = [0] # 쌓이는 인형 
    answer = 0

    for m in moves:
        for i in range(len(board)):
            if board[i][m-1] != 0 :

                if board[i][m-1] == doll[-1]:
                    answer += 2 
                    doll.pop()
                else: 
                    doll.append(board[i][m-1])
                board[i][m-1] = 0 
                break
        
    return answer

www.acmicpc.net/problem/9465

def sticker(n,data):

  data[0][1] += data[1][0] 
  data[1][1] += data[0][0] 

  for j in range(2,n):
    data[0][j] += max( data[1][j-2],  data[1][j-1] )
    data[1][j] += max ( data[0][j-2], data[0][j-1] )
  
  return max(data[0][n-1], data[1][n-1])

t = int(input())
t_print = []

for i in range(t):
  n = int(input())
  data = []
  for _ in range(2):
    data.append(list(map(int,input().split())))

  t_print.append ( sticker(n,data) )

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

index 2 이상부터 2칸 전 대각선과 1칸 전 대각선 비교해서 더하기가 가능! 

# 11725

from collections import deque 

n = int(input()) # 노드의 수 

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

def bfs():

  q = deque()
  q.append(1)
  visited = [0] * (n+1)
  visited[1] = 1

  while q :
    x = q.popleft()
    for i in tree[x]:

      if visited[i] == False:
        visited[i] = x
        q.append(i)
  
  return visited
    
result = bfs()

for i in range(2,len(result)):
  print(result[i])

visited 리스트에 부모 노드를 저장함. 

1 -> 1과 연결된 것의 부모를 1로 설정하고 방문 처리한 뒤, queue에 넣음 -> 반복..