플로이드 와샬

• 모든 점끼리의 최단거리를 알고싶을 때
• N이 작을 때 O(N^3)

프로그래머스 문제 - 배달

def solution(N, road, K):
    answer = 0
    graph = [[99999999]*N for i in range(N)]
    for i in range(N):
        graph[i][i] = 0
    for i in road:
        a, b, c = i
        graph[a-1][b-1] = min(c, graph[a-1][b-1])
        graph[b-1][a-1] = min(c, graph[b-1][a-1])
    for k in range(N):
        for i in range(N):
            for j in range(N):
                graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
    print(graph)
    for i in range(N):
        if graph[0][i] <= K: answer += 1
    return answer

dfs로 조합 구하기

백준 9997 폰트

• 뽑는 갯수 상관없이 모든 조합 구할 수 있음.

import sys

n = int(sys.stdin.readline())
words = [sys.stdin.readline().strip() for i in range(n)]
bitwords = []
alphabet = (1 << 26) - 1
answer = 0

for word in words:
    temp = 0
    for w in word:
        temp |= (1<<(ord(w)-ord('a')))
    bitwords.append(temp)


def dfs(depth, bit):
    global answer
    if depth == n-1 :
        if bit == alphabet:
            answer += 1
    else:
        dfs(depth+1, bit|bitwords[depth+1])
        dfs(depth+1, bit)

dfs(-1, 0)
print(answer)