희연's 개발 일기장

신장 트리(Spanning Tree)

- 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 그래프

신장 트리의 특징

1. 모든 노드를 포함

2. 사이클이 없음

3. 연결성 유지 : 그래프의 모든 노드를 연결

최소 신장 트리 (MST, Minimum Spanning Tree)

- 신장 트리에서 가중치의 합이 최소가 되는 신장 트리

- 알고리즘 종류 : 프림 알고리즘, 크루스칼 알고리즘

프림 알고리즘(Prim's Alogrithm)

- 시작 노드를 선택한다.

- 해당 노드와 가장 작은 가중치의 간선을 선택한다.

- 새로운 노드를 트리에 추가한다.

- 선택한 노드의 집합을 확장하면서 최소 신장 트리를 형성한다.

- 간선의 수가 적을 때 적합하다.

- Priority Queue 우선순위 큐 사용

- 시간 복잡도 : O(E log E) // E는 간선의 수

크루스칼 알고리즘(Kruskal's Alogrithm)

- 그래프의 간선을 가중치의 오름차순으로 정렬하고, 가장 작은 가중치부터 선택해서 최소 신장 트리를 구성한다.

- 사이클을 형성하지 않는 간선을 선택하면서 트리를 확장한다.

- 유니온 파인드(Union Find) 자료구조 사용으로, 사이클 여부 확인

- 그리디 알고리즘 사용

- 간선의 수가 많을 때 적합하다.

- 시간 복잡도 : O(E log V) // V는 노드의 수

[최소 신장 트리 알고리즘 예제]

백준 1414번

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

- N 개의 컴퓨터가 서로 연결되어 있는 랜선 길이가 주어질 때

- 모든 컴퓨터가 서로 연결되도록 만들고, 랜선 길이가 최대 값이 되는 값을 출력

- 파이썬 코드

def find(parent, x):  # 특정 원소가 속한 집합 찾기
    if parent[x] != x:  # 루트 노드가 아니면, 루트 노드 찾을 때까지 재귀
        return find(parent, parent[x])
    return parent[x]


def union(parent, a, b):  # 두 원소가 속한 집합 합치기
    a = find(parent, a)
    b = find(parent, b)
    if a < b:  # 더 작은 번호가 부모 노드
        parent[b] = a
    else:
        parent[a] = b


n = int(input())  # 컴퓨터 개수
edges = []
result = 0
parent = [i for i in range(n + 1)]  # 부모 테이블 초기화

for i in range(n):
    s = input()

    for j in range(len(s)):
        cost = 0  # 0이면 그대로
        ch = s[j]
        if ch.islower():  # 소문자
            cost = ord(ch) - ord('a') + 1
        elif ch.isupper():
            cost = ord(ch) - ord('A') + 27
        edges.append((cost, i + 1, j + 1))
        result += cost  # 모든 비용 계산

edges.sort()  # cost 오름차순 정렬

for cost, a, b in edges:
    if cost == 0:
        continue
    if find(parent, a) != find(parent, b):  # 사이클 발생 하지 않는 경우에 MST 포함
        union(parent, a, b)
        # print(cost)
        result -= cost

flag = True
for i in range(1, n + 1):
    if find(parent, i) != 1:
        flag = False

if flag:
    print(result)
else:
    print(-1)

백준 10423번

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

- 도시의 개수 N

- 설치 가능한 케이블 수 M

- 발전소 개수 K

- 모든 도시에 전기를 공급할 수 있도록 연결되어 있고, 케이블 설치 최소 비용 구하기

- 발전소가 설치된 도시는 연결하지 않아도 된다.

- 파이썬 코드

def find(parent, x):
    if parent[x] != x:
        return find(parent, parent[x])
    return parent[x]


def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


n, m, k = map(int, input().split())  # 도시 개수, 케이블 수, 발전소 개수
numbers = list(map(int, input().split()))  # 발전소 설치된 도시 번호
parent = [i for i in range(n + 1)]
edges = []
answer = 0

for num in numbers:  # 발전소 설치된 도시의 루트를 0 으로 초기화
    parent[num] = 0

for _ in range(m):
    u, v, w = map(int, input().split())  # u 도시와 v 도시 연결 비용 w
    edges.append((w, u, v))

edges.sort()

for cost, a, b in edges:
    if find(parent, a) != find(parent, b):  # 사이클이 아닌 경우에만 계산
        union(parent, a, b)
        answer += cost

print(answer)

정규 표현식(regular expression)

- 특정한 규칙을 가진 문자열의 집합을 표현하는 데 사용하는 형식 언어

- regexp, regex

정규 표현식 메타 문자(meta characters)

- 문자가 가진 뜻이 아닌 특별한 용도로 사용하는 문자

. ^ $ * + ? { } [ ] \ | ( )

문자 클래스(character class) [ ]

- [ ] 사이의 문자들과 매치

ex) [abc] = a, b, c 중에 한 개의 문자와 매치

- 문자 사이에 하이픈(-)을 사용하면 두 문자 사이의 범위가 된다.

ex) [a-c] = [abc], [0-5] = [012345]

- [a-zA-Z] 알파벳 전부

- [0-9] 숫자 

^ 메타 문자

- not 의미를 갖는다.

ex) [^0-9] = 숫자가 아닌 문자

자주 사용하는 문자 클래스

Dot(.) 메타문자

- \n 을 제외한 모든 문자와 매치

ex) a.b = a + 모든문자 + b

- aab, a0b는 정규식과 매치된다.

문자열을 앞이나 뒤에 매치할 때

- 맨 앞 : ^

ex) ^foo = foo + 아무거나

- 맨 뒤 : $ 

- 문자열이 $ 앞에 있는 문자로 끝나면 매치된다.

ex) abc$ = 아무거나 + abc

반복 (*)

- 반복을 의미하는 메타 문자

- *은 *앞에 있는 문자가 무한대로 반복될 수 있다.

반복 (+)

- 최소 1번 이상 반복될 떄 사용한다.

반복 ({m, n}, ?)

- 반복 횟수를 제한할 때 사용

- m부터 n까지 

ex) {3,} = 반복 횟수 3 이상

ex) {,3} = 반복 횟수 3 이하

? 메타 문자

- {0, 1} 을 의미한다.

정규 표현식을 지원하는 re 모듈

import re
p = re.compile('abc')

컴파일된 패턴 객체가 제공하는 메서드

match

- 문자열의 처음부터 정규식과 매치되는지 조사한다.

- 처음부터 끝까지 전부 일치해야 하는경우 -> fullmatch 사용

# 패턴 만들기
import re
p = re.compile('[a-z]+')

# match 매치 확인
m = p.match('3 python')
print(m) # None : 3이 [a-z]+ 에 매치 되지 않는다

# search
m = p.match('3 python')
print(m) # <re.Match object; span=(2, 8), match='python'>
# search는 문자열을 전체를 검색하기 때문에 매치된다.

findall

result = p.findall("life is too short")
print(result) 
# ['life', 'is', 'too', 'short']
# [a-z]+ 와 매치되는 모든 값을 리스트로 리턴

finditer

result = p.finditer("life is too short")
print(result)
<callable_iterator object at 0x01F5E390>
for r in result: print(r)
...
<re.Match object; span=(0, 4), match='life'>
<re.Match object; span=(5, 7), match='is'>
<re.Match object; span=(8, 11), match='too'>
<re.Match object; span=(12, 17), match='short'>

match 객체의 메서드

m = p.match("python")
m.group() # 'python'
m.start() # 0
m.end() # 6
m.span() # (0, 6)

문제 풀이

https://hhiyeon.tistory.com/245

https://hhiyeon.tistory.com/246

https://hhiyeon.tistory.com/247

https://hhiyeon.tistory.com/248

https://hhiyeon.tistory.com/249

https://hhiyeon.tistory.com/250

https://hhiyeon.tistory.com/251

비트마스크(bitmask)

• 원소의 수가 많지 않을 때 사용
• 집합을 배열의 인덱스로 표현할 때 사용한다.
• 이진수로 비트 연산을 활용하는 방법

비트마스크 활용

• [1,2,3,4,5] 집합이 있을 때 부분 집합을 만든다.
• [1], [2], ... ,[1,2],[1,3], ... , [1,2,3], ... [1,2,3,4,5]
• 비트 마스크를 사용하면 각 요소를 인덱스로 표현하여 효율적인 접근이 가능하다.
• [1,2,3,4,5] -> 11111
• [2,3,4,5] -> 11110
• [1,2,5] -> 10011

비트의 연산

• AND, OR, NOT, XOR

쉬프트(Shift) 연산자

• << : 왼쪽 시프트, A * 2^B, 0001 -> 0010 -> 0100 -> 1000 : 1 -> 2 -> 4 -> 8
• >> : 오른쪽 시프트, A / 2^B 1000 -> 0100 -> 0010 -> 0001 : 8 -> 4 -> 2 -> 1
• N&1 : N이 짝수인지 홀수인지 구하기 위해 2로 나눈 나머지를 1과 비교하는 연산, N%2==1

삽입, 삭제, 조회

• 삽입(OR)
  • 이진수가 10101일 때, i 번째 비트 값을 1로 변경하려고 한다. i=3일 때 변경 후에는 11101
  • 10101 | 1 << 3 
  • 10101 | 01000 = 11101
• 삭제(AND, NOT)
  • 11101 & ~1 << 3
  • 11101 & 10111 = 10101
• 조회(AND)
  • 10101 & 1 << i
  • 3번째 비트 값 : 10101 & 01000 = 0
  • 4번째 비트 값 : 10101 & 10000 = 10000

비트마스킹 문제 - 1094번 막대기

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

x = int(input())
x = bin(x)
answer = 0
# 가지고 있는 막대 길이 모두 더하기
# 합이 X보다 크면 , 가장 길이 짧은 것을 절반으로 자르기
# 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같으면 위에서 자른 막대의 절반 중 하나를 버린다.

for i in x:
    if i == '1':
        answer += 1
print(answer)

비트마스킹 문제 - 11723번 집합

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

#M = 26 # 연산의 수
import sys
M = int(sys.stdin.readline())
S = 0 # 공집합

for _ in range(M):
    command = sys.stdin.readline().split()
    opt = command[0]
    if len(command)>1:
        x = int(command[1]) - 1

    if opt == 'add': # S에 x를 추가한다.
        S = S | (1 << x)
    elif opt == 'remove': # S에서 x를 제거한다.
        S = S & ~(1 << x)
    elif opt == 'check': # S에 x가 있으면 1을, 없으면 0 출력
        if S & (1 << x) == 0:
            print(0)
        else:
            print(1)
    elif opt == 'toggle': # S에 x가 있으면 x 제거, 없으면 x 추가
        S = S ^ (1 << x)
    elif opt == 'all': # S를 {1,2, ..., 20} 으로 바꾼다.
        S = (1 << 20)-1
    elif opt == 'empty': # S를 공집합으로 바꾼다
        S = 0

다익스트라(Dijkstra) 알고리즘

• 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘
• 음수의 가중치가 없을 때 사용 -> 음수 가중치 있는 경우 벨만포드 알고리즘

다익스트라 알고리즈 구현 과정 - O(N^2)

1. 출발 노드 설정

2. 출발 노드 기준으로 노드의 각 최소 비용 저장

3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택

4. 해당 노드를 거쳐서 특정 노드로 가는 경우를 고려해서 최소 비용 갱신

5. 3~4번 반복

다익스트라 알고리즈 구현 과정 - 힙 사용 O(N*logN)

다익스트라 문제 - 1753번 최단경로

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

import heapq
import sys
input = sys.stdin.readline
#V, E = 5, 6  # 정점의 개수, 간선의 개수
V, E = map(int, input().split())
K = int(input())
#k = 1  # 시작 정점의 번호
inf = float('inf')
graph = [[] for _ in range(V + 1)]
distance = [inf]*(V+1) # 가중치 테이블 dp
pq = []  # 우선순위 큐

for _ in range(E):
    u, v, w = map(int, input().split())  # u에서 v로 가는 가중치 w 간선
    graph[u].append((v, w))

def dijkstra(start):
    distance[start] = 0
    heapq.heappush(pq, [0, start])  # 거리, 시작 정점 번호

    while pq: # 우선순위 큐를 사용해서 가장 최단 거리의 노드 고르기
        dist, now = heapq.heappop(pq)

        # 현재 노드가 이미 방문된 기록이 있으면 무시
        if distance[now] < dist:
            continue

        # 현재 노드와 연결된 노드들을 확인
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]: # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
                distance[i[0]] = cost # 가중치르 갱신 해준다.
                heapq.heappush(pq, [cost, i[0]])

dijkstra(K)

for i in distance[1:]:
    if i == inf:
        print("INF")
    else:
        print(i)

플로이드 와샬(Floyd Warshall)

• 모든 정점에서 모든 정점으로의 최단 경로를 구하기 위해 사용하는 알고리즘
• 무방향, 방향 그래프에서 사용 가능하지만 음수 사이클이 있으면 X

플로이드 와샬 구현 방법

• 일단 자기 자신은 0, 간선 1개로 얻을 수 있는 값들로 2차원 배열(최단 거리 테이블)을 만든다.
• x에서 y로 가는 최소 비용 vs x에서 노드1으로 가는 최소 비용 + 노드 1에서 y로 가는 최소 비용
  • ex. D[2, 3] = min((D[2,1] + D[1,3]), D[2,3])
• 1부터 n까지의 노드들 최소 비용 갱신

플로이드 와샬 문제 - 11404번 플로이드

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

#n = 5 # 도시의 개수
#m = 14 # 버스의 개수
n = int(input())
m = int(input())
inf = float('inf')
dp = [[inf for _ in range(n+1)] for _ in range(n+1)] # 최소 비용 테이블
# 버스의 정보 : 시작 도시 a, 도착 도시 b, 필요 비용 c
for _ in range(m):
    a, b, c = map(int, input().split())
    dp[a][b] = min(c, dp[a][b])

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i == j: # 자기 자신은 X
                dp[i][j] = 0
            else:
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

for x in range(1, n+1):
    for y in range(1, n+1):
        if dp[x][y] == inf:
            print(0, end=' ')
        else:
            print(dp[x][y], end=' ')
    print()

위상 정렬(Topological Sort)

• 방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬
• ex. 선수 과목 : 특정 과목에 선수 과목이 있을 경우 선수 과목부터 수강해야 하는 상황에서 위상정렬으로 순서 찾기 
• 그래프 순환이 존재하지 않아야 한다.
• DAG(Directed Acyclic Graph) : 사이클이 존재하지 않는 방향 그래프

위상 정렬의 수행 과정

1. 자기 자신을 가리키는 변이 없는 꼭짓점을 찾는다.

2. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제한다.

3. 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료한다.

위상 정렬 알고리즘

1. 맨 처음 모든 간선을 읽으며 indegree 테이블을 채운다.

2. indegree가 0인 정점들을 모두 큐에 넣는다.

3. 큐에서 정점을 꺼내 위상 정렬 결과에 추가한다.

4. 해당 정점으로부터 연결된 모든 정점의 indegree 값ㅇ르 1 감소시키고, indegree가 0이 되면 정점을 큐에 추가한다.

5. 큐가 빌 때까지 3,4번을 반복

위상 정렬 문제 - 2252번 줄 세우기 

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

from collections import deque
#n, m = 3, 2 # 학생의 번호 1~n, m는 키를 비교환 횟수
n, m = map(int, input().split())
inDegree = [0]*(n+1)
graph = [[] for i in range(n+1)]
queue = deque()
answer = []
arr = []
# 1 -> 3
# 2 -> 3

# 키를 비교한 두 학생의 번호 a,b (학생 a가 b앞에)
# 그래프에 정점끼리 연결된 정보들 입력
for _ in range(m):
    a, b = map(int, input().split())
    arr.append([a,b])

for a, b in arr:
    inDegree[b] += 1
    graph[a].append(b)

for i in range(1, n+1):
    if inDegree[i] == 0:
        queue.append(i)

while queue:
    top = queue.popleft() # 큐 최상위 정점
    for b in graph[top]:
        inDegree[b] -= 1
        if inDegree[b] == 0:
            queue.append(b)
    answer.append(top)

print(*answer)

깊이 우선 탐색 DFS(Depth First Search)

• 하나의 루트에서 탐색하다가 특정 상황에서 깊게 들어가서 확인하고 다시 돌아와서 다른 루트로 탐색하는 방법
• 백트래킹에서 사용
• 재귀, 스택으로 구현

구현 과정

• 탐색 시작 노드를 스택에 넣고 방문 처리
• 스택에서 원소를 꺼내서 방문하지 않은 인접 노드가 있을 경우 그 노드를 스택에 넣고 방문 처리
• 스택이 빌때까지 반복

DFS 문제 - 2468번 안전 영역

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

DFS 문제 - 10026번 적록색약

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

DFS 문제 - 1987번 알파벳 

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

BFS(Breadth First Search) 너비 우선 탐색

• 가중치가 없는 그래프에서 시작점에서 끝점까지의 최단 경로를 찾을 수 있다.
  • 가중치가 있는 그래프에서는 '다익스트라' 알고리즘 사용
• 주로 Queue를 이용해서 구현한다.
• 노드의 개수 N, 시간복잡도 O(N)

구현 과정

• 탐색을 시작하는 칸을 큐에 넣고 방문 처리
• 큐에서 pop해서 방문하지 않은 노드의 상하좌우로 인접한 노드 정보를 모두 큐에 넣고 현재 노드(pop한 노드) 방문처리 한다.
• 큐가 빌때까지 반복

BFS 문제 - 1926번 그림

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

from collections import deque

n, m = map(int, input().split())  # 세로, 가로
board = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
answer = []  # 넓이를 저장할 리스트


# 그림의 개수, 가장 큰 넓이 출력
# 그림 = 1로 연결된 것,

def bfs(x, y):  # 탐색 위치, 넓이
    # 그림이 시작 하는 위치에서 큐 시작
    board[x][y] = 0  # 현재 위치 방문 체크
    queue = deque()  # 큐 생성
    queue.append([x, y])  # 큐에 해당 칸 넣기
    cnt = 1  # 그림 칸 개수
    while queue:  # 큐가 빌때까지
        a, b = queue.popleft()  # 현재 탐색 위치 제거(탐색 완료)
        for d in range(4):  # 상하좌우 확인
            nx = a + dx[d]
            ny = b + dy[d]
            # 2차원 배열에서 벗어나지 않고, 다음 위치가 1(그림이 있는)인 경우
            if -1 < nx < n and -1 < ny < m and board[nx][ny] == 1:
                board[nx][ny] = 0  # 다음 위치 방문 체크
                queue.append([nx, ny])  # 큐에 탐색할 위치 넣기
                cnt += 1  # 그림 칸 개수
    return cnt


# 그림의 시작점 찾기
for i in range(n):
    for j in range(m):
        if board[i][j] == 1:  # 그림이 있는 위치
            answer.append(bfs(i, j))

if len(answer) == 0: # 그림이 하나도 없는 경우
    print(len(answer))
    print(0)
else:
    print(len(answer))
    print(max(answer))

BFS 문제 -2667번 단지번호붙이기

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

from collections import deque

n = int(input())
board = [list(map(int, input())) for _ in range(n)]
answer = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


# 1 집이 있는곳, 0 집이 없는 곳
# 단지 개수, 단지에 속하는 집 개수 출력

def bfs(x, y):
    queue = deque()
    queue.append([x, y])
    board[x][y] = 0  # 방문체크
    cnt = 1

    while queue:
        px, py = queue.popleft()

        for d in range(4):
            nx = px + dx[d]
            ny = py + dy[d]

            # 방문 가능한 곳인지 확인
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 1:
                board[nx][ny] = 0  # 다음 방문 체크
                queue.append([nx, ny])  # 큐 입력
                cnt += 1
    return cnt  # 집 개수 출력


for i in range(n):
    for j in range(n):
        if board[i][j] == 1:
            answer.append(bfs(i, j))

answer.sort()
print(len(answer))
for x in answer:
    print(x)

BFS 문제 - 2178번 미로 탐색

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

from collections import deque

n, m = map(int, input().split())  # 가로, 세로
board = [list(map(int, input())) for _ in range(n)]

# 1: 이동할 수 있는 칸, 0: 이동 불가능
# (1,1)에서 출발 (N,M) 위치로 이동할 때 지나야 하는 최소 칸 수 출력

def bfs(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    queue = deque()  # 큐 생성
    queue.append([x, y])  # 시작점 체크
    while queue:
        a, b = queue.popleft()

        for d in range(4):
            nx = a + dx[d]
            ny = b + dy[d]

            # 방문 가능한 곳
            if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 1:
                queue.append([nx, ny])  # 큐 삽입
                board[nx][ny] = board[a][b] + 1
    return board[n - 1][m - 1]

print(bfs(0,0))

BFS 문제 - 7576번 토마토

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

from collections import deque

m, n = map(int, input().split())  # 가로, 세로
board = [list(map(int, input().split())) for _ in range(n)]
visited = [[0 for _ in range(m)] for _ in range(n)]
queue = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
day = 0

# 토마토는 하루가 지날 때 마다 안익은 토마토는 인접한 익은 토마토의 영향을 받아 익게 된다.
# 모든 토마토가 익게 되는 일수 출력, 모두 익지 못하는 상황에는 -1 출력
# 익은 토마토 1, 안익은 토마토 0, 토마토가 없는 경우 -1
# 시작 위치 큐에 넣기
for i in range(n):
    for j in range(m):
        if board[i][j] == 1:
            queue.append([i, j])

def bfs():
    while queue:
        px, py = queue.popleft()

        for d in range(4):
            nx = px + dx[d]
            ny = py + dy[d]

            # 토마토가 익지 않았을 경우
            if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 0:
                board[nx][ny] = board[px][py] + 1
                queue.append([nx, ny])


bfs()

# 익지 않은 토마토가 있으면 -1 출력, 모두 다 익은 경우 가장 큰 날짜를 찾아서 출력
for i in range(n):
    for j in range(m):
        if board[i][j] == 0:
            print(-1)
            exit(0)
    maxValue = max(board[i])
    day = max(maxValue, day)

# 처음 시작을 1로 했기 때문에 -1
print(day-1)

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

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

from collections import deque
#n, k = 5, 17 # 수빈이가 있는 위치, 동생이 있는 위치
n, k = map(int, input().split())
MAX = 10 ** 5
visited = [0]*(MAX+1)
# 걷기 : 1초 후 x-1, x+1로이동
# 순간이동 : 1초 후 2*x 으로 이동
# 가장 빠른 시간 찾기

def bfs():
    queue = deque()
    queue.append(n)
    while queue:
        x = queue.popleft()

        if x == k:
            print(visited[x])
            break
        for nx in (x-1, x+1, x*2):
            if 0 <= nx <= MAX and not visited[nx]:
                visited[nx] = visited[x] + 1
                queue.append(nx)

bfs()

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

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

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

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