[Python/BOJ] 백준 1039 교환_(신박한)BFS

 

BFS를 맨날 이차원 리스트에서만 보다가 이렇게 문자열에서 처리하는 문제를 보니 참 신박하다.

 

 

 

vis를 set으로 하여 방문여부를 확인하였다. set은 튜플형태로만 add가 된다. (list는 안됨)

덱에 [n,0]와 vis에 [n,0]이 넣어지면서 시작한다. 

n은 현재 숫자이고 0은 변경횟수를 의미한다.

 

---

 

 

1. 덱이 있는 동안 반복한다.

 

1-1 . 덱에서 왼쪽에 있는 값을 꺼낸다.

1-2. 만약 변화 횟수가 K라면 ans를 갱신한다.

1-3.  int는 []으로 접근할 수 없으므로 str -> list로 만들어 하나씩 접근할 수 있도록 만든다.

1-4. 이중 for문을 돌면서 변경할 수 있는 모든 경우를 다 본다. 

1-5. 첫번째 자리가 i이고 j의 값이 0인 경우 continue한다. 첫번째 자리에 0이 들어가면 안되기 때문이다.

1-6. 문자열을 변경한후 vis를 확인한다.

1-7. vis에 없을 경우 덱에 넣고 vis에 넣는다. 

 

2. ans가 초기값인 경우 -1을 초기값이 아닐 경우 ans값을 출력한다. 

 

 

 

 

코드 : 

from collections import deque
         
def bfs(n,K) :
    # 방문 확인 
    vis = set()
    # n을 0번 변화로 만들 수 있다. 
    vis.add((n,0))
    d = deque()
    d.append([n,0])
    ans = 0
    while d :
        num,k = d.popleft()
        if k == K :
            ans = max(ans,num)
            continue 
        num = list(str(num))
        # i 와 m 사이에는 j가 있어야하므로 m-1까지 
        for i in range(m-1) : 
            for j in range(i+1,m) :
                # 첫번째 자리에 0이 옮겨진다면
                if i == 0 and num[j] == '0' :
                    continue
                num[i],num[j] = num[j],num[i]
                # i와 j의 순서를 바꾼 문자열을 합친후 숫자로 만듦
                nn = int(''.join(num))
                if (nn,k+1) not in vis :
                    d.append([nn,k+1])
                    vis.add((nn,k+1))
                num[i],num[j] = num[j],num[i]
    return ans if ans else -1 
                
                

if __name__=="__main__" :
    n,K = map(int,input().split())
    m = len(str(n))
    print(bfs(n,K))

 

 

 

 

 

참고 블로그 : 

https://2hs-rti.tistory.com/entry/%EB%B0%B1%EC%A4%80-1039%EB%B2%88-%EA%B5%90%ED%99%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC

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