๋ฌธ์
๋ฐฑ์ค 1039 ๊ตํ ๋ฌธ์ ๋ฅผ ํ์์ต๋๋ค.
๋๋ฌด ์ด๋ ต๊ฒ ์๊ฐํ ๋ฌธ์ ๊ฐ ์๋์๋ ๊ฒ ๊ฐ์ต๋๋ค.
- ํํธ 1 : BFS ๋ง๊ธด ํฉ๋๋ค.
- ํํธ 2 : ์์ ํ์๊ณผ ๋ค๋ฅผ ๋ฐ ์์.
- ํํธ 3 : ์๊ฐ ์ด๊ณผ๋ ๊ฒ ๊ฐ์๋ฐ..? ํ์๊ฒ ์ง๋ง ์๋ฉ๋๋ค. BFS๋ก ์ํํ๋ฉฐ ์์ ํ์ํ์๋ฉด ๋ฉ๋๋ค.
ํ์ด
BFS๋ก K๋ฒ์ ์ฐ์ฐ์ ์์ ํ์ํด์ค๋๋ค.
์ฐ์ฐ ๊ตฌํ์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
16375์ธ ๊ฒฝ์ฐ์์ K=1 ์ฐ์ฐ
์์ ํ : 16375
while q, q์์ 16375๋ฅผ ๊บผ๋ด์ ์ฐ์ฐ ์์.
- โ1โ์ 6, 3, 7, 5์ ๋ฐ๊พผ๋ค. ๊ทธ ๊ฒฐ๊ณผ๋ฅผ ํ์ ๋ฃ๋๋ค.
- Q : 61375 36175 76315 56371
- โ6โ์ 3,7,5์ ๋ฐ๊พผ๋ค. ๊ทธ ๊ฒฐ๊ณผ๋ฅผ ํ์ ๋ฃ๋๋ค.
- Q : 61375 36175 76315 56371 13675 17365 15376
- โ3โ์ 7,5์ ๋ฐ๊พผ๋ค. ๊ทธ ๊ฒฐ๊ณผ๋ฅผ ํ์ ๋ฃ๋๋ค.
- Q : 61375 36175 76315 56371 13675 17365 15376 16735 16573
- โ7โ์ 5์ ๋ฐ๊พผ๋ค. ๊ทธ ๊ฒฐ๊ณผ๋ฅผ ํ์ ๋ฃ๋๋ค.
- Q : 61375 36175 76315 56371 13675 17365 15376 16735 16573 16357
๋จ, Q์ ๋ค์ด๊ฐ๋ ๊ฐ์ด 0์ผ๋ก ์์ํ์ง ์๊ณ ์ด๋ฏธ ํ์ ์์ง ์์ ๊ฒฝ์ฐ์๋ง ๋ฃ์ด์ค๋๋ค. (๊ฐ๋ น 1111 ์ด๋ฉด ๋ฌด์๋ฏธํ๊ฒ ๊ฐ์ ๊ฐ๋ง ๋ง์ด ๋ค์ด๊ฐ๊ฒ ์ฃ ? ๊ตณ์ด ๋ฃ์ ํ์ ์์ผ๋ ์๋ฃ๊ฒ ์ต๋๋ค.)
๊ทธ๋ฐ๋ฐ ์ด์ ๋ช ๋ฒ ์ฐ์ฐ์ ํ๋์ง๋ฅผ ๊ผญ ์ธ์ด์ค์ผํฉ๋๋ค. ๊ทธ๋์ Q์๋ ๊ฒฐ๊ณผ์ซ์๊ฐ๊ณผ, ์ฐ์ฐํ์(tempK)๋ฅผ ํจ๊ป tuple๋ก ๋ฌถ์ด์ ๋ฃ์ด์ฃผ์์ต๋๋ค. (๋ด๋ถ์ ์๋ ๊ฐ์ด ๋ฐ๋์ง ์์ ๊ฒ์ด๋ฉฐ, ๋ฐ๋์ด์๋ ์๋๊ธฐ ๋๋ฌธ์ ํํ๋ก ๋ฃ์ด์ฃผ์์ต๋๋ค. ํด๋จผ ์๋ฌ๋ก ์ด๋์ ๊ฐ ๊ฐ์ด ๋ฐ๋๊ณ ์๋ค๋ฉด ์ปดํ์ผ ์๋ฌ๋ฅผ ๋ด๋๋ก์.)
๊ทธ๋์, K๋ฒ ์ฐ์ฐ์ด ๋๋ฌ๋ค๋ฉด, K+1๋ฒ์งธ ์ฐ์ฐ์ ์์ํ๊ธฐ ์ง์ ์ while ๋ฌธ์์ ํ์ถํด์ค๋๋ค.
- ์ ํํ๋ ๊ทธ๋ฅ ๊ฐ์ฅ ํฐ ๊ฐ์ ์ฐพ์์ return ํด์ฃผ์๋ฉด ๋ฉ๋๋ค. ์๋ํ๋ฉด ์ ์์ ์ผ๋ก while๋ฌธ์์ ํ์ถ๋์๋ค๋ฉด, ์ฆ q๊ฐ ํ ๋น๋ ์ฌํ๊ฐ ๋ฐ์ํ๋ค๋ฉด ์ด๋ K๋ฒ๊น์ง ์ฐ์ฐ์ ๋ชปํ๊ณ โ๋ค์์ ๊ณ์ฐํ ์๋ฅผ ๋ชป์ฐพ์โ ๊ฒฝ์ฐ์ด๊ธฐ ๋๋ฌธ์ ๋๋ค. (-1์ ๋ฑ์ด์ผ ํ๋ ์์ธ ์ฌํญ๋ค์ด ์ด๋ฐ ์ผ์ด์ค์ ํด๋นํฉ๋๋ค. ์์ธ ์ฌํญ์ผ๋ก ๊ณ ๋ คํด์ฃผ์ ์ผํ๋ ์ผ์ด์ค๋ ํ๋จ์ ์ ๊ฒ ์ต๋๋ค.)
- ์ ํํ K+1๋ฒ์งธ ์ฐ์ฐ์ ์์ํ๊ธฐ ์ง์ ์ผ๊น์? ํ์ ๋จ์์์ ๋ ธ๋๋ค์ ์๊ฐํด๋ณด๋ฉด ์ฝ์ต๋๋ค. 2๋ฒ์งธ ์ฐ์ฐ์ด ์์๋๋ ์์ ์, 1๋ฒ์งธ ์ฐ์ฐ์ ํตํด ์ป์ ์ ์๋ ๋ชจ๋ ๊ฒฐ๊ณผ๊ฐ๋ค์ ์ ๋ถ ์ป์ด์ ํ์ ๋ฃ์์ ๋์ ๋๋ค. ์ฐ๋ฆฌ๋ K๋ฒ์งธ ์ฐ์ฐ์์ ๋์จ ๋ชจ๋ ๊ฐ์์ ์ต๋๊ฐ์ ๊ตฌํด์ผ ํ๋ฏ๋ก, K+1๋ฒ์งธ ์ฐ์ฐ์ด ์์ํ๊ธฐ ์ , ์ฆ ํํ๋ก BFS ๋ ธ๋์ ํจ๊ป ๋ฌถ์ฌ์ ธ์๋ โ์ฐ์ฐ ํ์โ๊ฐ K๊ฐ ๋๋ ์๊ฐ์ returnํด์ฃผ๋ฉด ๋ฉ๋๋ค.
์์ธ์ฒ๋ฆฌ๋ฅผ ๊ณ ๋ คํ์ ์ผ ํ๋ ์ผ์ด์ค๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
- 0, 1, 2, 3, โฆ, 9 ๋ฑ ํ์๋ฆฌ ์
- 0์ผ๋ก ๋๋๋ ๋์๋ฆฌ ์ (0์ด ์์ผ๋ก ๊ฐ๋ฉด ์๋๊ธฐ ๋๋ฌธ์ ๋๋ค.)
- 0์ผ๋ก ๋๋๋ n์๋ฆฌ ์(n>=3)์์? : ์์ธ๊ฐ ์๋๋๋ค. 100์ธ ๊ฒฝ์ฐ์๋ 0๊ณผ 0์ด ์๋ฆฌ๋ฅผ ๋ฐ๊พธ์ด 100์ด๋ผ๋ ๊ฐ์ ๋ง๋ค ์ ์์ต๋๋ค.
while loop์์ ์ ์ ํ๊ฒ ํ์ถํ๊ณ ์๋ค๋ฉด ๋ณ๋์ ์์ธ๋ฅผ ์์ฑํ์ง ์์๋ ์ ์์ ์ผ๋ก ๋์ํฉ๋๋ค.
๋ต
from collections import deque
def bfs(start, K) :
startK = 0
q = deque([(start, startK)])
while q :
if (q[0])[1] == K :
return max(x[0] for x in q)
tempStart, tempK = q.popleft()
for i in range(0,len(start)-1) :
for j in range(i+1, len(start)) :
tempN = list(tempStart)
tempN[j], tempN[i] = tempN[i], tempN[j]
tempN = ''.join(tempN)
if tempN[0] != '0' and (tempN,tempK+1) not in q :
q.append((tempN,tempK+1))
return -1
def _1039() :
N, K = map(int, input().split())
print(bfs(str(N), K))
_1039()