[백준] 1039번 - 교환 (파이썬)

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

 

# 교환
from collections import deque
N, K = map(int, input().split())
M = len(str(N))


def bfs(N, K):
    visited = set()
    visited.add((N, 0))
    q = deque()
    q.append((N, 0))
    answer = 0
    while q:
        n, k = q.popleft()
        if k == K:
            answer = max(answer, n)
            continue
        n = list(str(n))
        for i in range(M-1):
            for j in range(i+1, M):
                if i == 0 and n[j] == '0':
                    continue
                n[i], n[j] = n[j], n[i]
                nn = int(''.join(n))
                if (nn, k+1) not in visited:
                    q.append((nn, k+1))
                    visited.add((nn, k+1))
                n[i], n[j] = n[j], n[i]
    return answer if answer else -1


print(bfs(N, K))

 

BFS
1. 입력을 받는다 (M : 자릿수)
2. bfs
    - visited : 방문 여부 ( 집합으로 중복제거)
    - (바꾼 값, 총 교체 횟수)가 visited에 없다면 q에 append, visited에 add
    - 첫째 자리와 바꿀 값이 0이면 ( i==0, n[j] =='0') 바꿀 수 없음
    - 총 교체 횟수가 K라면 answer에 최댓값 설정
    - answer가 0이 아니라면 answer, else -1 리턴
3. bfs 실행 값 출력

 

visited를 집합으로 정의해서 계속 추가해 주었다.

숫자를 문자열화이후, 리스트화하여 스왑을 진행해주었다.