[백준] CLASS 3 달성하기 2일차

이진규·2022년 7월 10일
1

백준(PYTHON)

목록 보기
48/115

1. 케빈 베이컨의 6단계 법칙(BFS)

링크 : https://www.acmicpc.net/problem/1389

from sys import stdin
from collections import deque
input = stdin.readline

n, m = map(int, input().split())
graph = [ [] for _ in range(n+1) ]
answer = [] # 모든 단계를 거친 합을 저장할 배열

for _ in range(m): # 양방향 그래프
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def bfs(x, step): # 유저와 단계를 넘겨 받음
    visited = [False] * (n+1)
    visited[x] = True
    step_arr = [0] * (n+1) # 단계를 저장할 배열
    q = deque([(x, step)])

    while q:
        node, step = q.popleft()

        step_arr[node] = step # 해당 유저에 해당하는 단계를 저장

        for i in graph[node]:
            if not visited[i]:
                visited[i] = True
                q.append((i, step+1))

    answer.append(sum(step_arr))

for i in range(1, len(graph)): # 1번 유저부터 차례대로 BFS를 탐색
    bfs(i, 0)

min_step = min(answer) # 모든 단계의 합을 저장한 배열의 최소값을 구해서 인덱스를 구한다.
print( answer.index(min_step) + 1 )

2. 1로 만들기(★DP)

링크 : https://www.acmicpc.net/problem/1463

  • 큰 수 부터 줄어드는 게 아니라 1부터 시작하는게 핵심
from sys import stdin
input = stdin.readline

n = int(input())

dp = [0] * (n+1)

for i in range(2, n+1):

    dp[i] = dp[i-1] + 1

    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)

print(dp[n])

3. 잃어버린 괄호(문자열 파싱)

링크 : https://www.acmicpc.net/problem/1541

from sys import stdin
input = stdin.readline

num = input().rstrip().split('-')

answer = []
ans = 0

for i in num:
    tmp = 0
    for j in i.split('+'):
        tmp += int(j)

    answer.append(tmp)

for i in range(len(answer)):
    if i == 0:
        ans = answer[0]
    else:
        ans -= answer[i]

print(ans)

4. 나는야 포켓몬 마스터 이다솜(★딕셔너리)

링크 : https://www.acmicpc.net/problem/1620

  • 딕셔너리의 key로 포켓몬 번호와, 포켓몬 이름 둘다 주는게 포인트임
    괜히 딕셔너리의 key로 포켓몬 번호만 설정하고 검색 조건이 포켓몬 번호일땐 get()으로 포켓몬 이름일땐 items()로 반복문을 돌려 value를 찾을때 key를 출력 할려고 하다가 시간복잡도 걸림
from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
pokemon_dict = {}

for i in range(1, n+1): # 딕셔너리의 key로 포켓몬 번호와, 포켓몬 이름 둘다 주는게 포인트
    pokemon = input().rstrip()
    pokemon_dict[str(i)] = pokemon
    pokemon_dict[pokemon] = int(i)


for _ in range(m):
    search = input().rstrip()

    print(pokemon_dict[search])
profile
항상 궁금해하고 공부하고 기록하자.

0개의 댓글