소수 경로 [백준 1963]

1. 문제 접근 방법

- DFS로 접근해서 문제를 해결했다

-> 한 번 접근했던 곳을 중복 접근할 때는, 방문횟수가 더 적은 경우에만 접근하도록 하는 것이 중요하다

-> 또한, 숫자를 바꿀때는 최대한 목표와 가까운 것부터 바꾸게 하는 것이 중요하다

-> 왜냐면 그래야 가장 최소 횟수로 접근할 확률이 높아지기 때문이다.

-> 또한, 최소 횟수를 넘은 케이스에 대해서 pruning해주는 것도 중요하다. 

 

- Memoization에 대해서 좀 더 제대로 할 필요가 있다

-> 즉, 난이도가 높은 문제일수록 최적화가 중요한 문제로 대두된다는 점을 기억해야 한다

-> DP에 대해서 좀 더 제대로 공부할 필요가 있다. 

 

- 또한 소수를 구하는 로직에 대해서도 익숙하게 구현해야 한다

-> sqrt를 사용해서 구하는 것에 익숙해져야 한다 

 

- 다른 사람 코드를 보고 학습을 진행해야겠다. 

 

- 이 문제는 BFS로 푸는 것이 좋다

-> 왜냐하면 BFS로 풀면, 저절로 Memoization을 고려할 필요가 없이, 가능하기 때문이다. 

-> 일종의 '최단거리' 문제로 볼 수 있으므로, BFS로 푸는 것이 적합하다. 

 

 

2. 내 코드

import math

T = int(input())
prime = [False]*10000
visited = [False]*10000
minCnt = int(1e9)


def isPrime(num):

    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0:
            return False
    return True


for i in range(1000, 10000):
    if isPrime(i) == True:
        prime[i] = True


def dfs(curr, end, cnt, path):
    
    
    global minCnt 
    
    if minCnt < cnt:
        return 
    
    if curr == end:
        minCnt = min(minCnt, cnt)
        return 
    
    
    one = curr // 1000
    two = (curr - 1000*(one)) // 100
    three = (curr - 1000*one-100*two) // 10
    four = curr % 10 
    
    endOne = end // 1000
    endTwo = (end - 1000*(endOne)) // 100
    endThree = (end - 1000*endOne-100*endTwo) // 10
    endFour = end % 10 
    
    
    newCurr = 0 
    
    for i in range(4): 
            if i == 0:         
                if one == endOne:
                    continue
                
                newCurr = endOne*1000+two*100+three*10+four
            elif i == 1:
                if two == endTwo:
                    continue
                
                newCurr = one*1000+endTwo*100+three*10+four
            elif i == 2:
                if three == endThree:
                    continue
                
                newCurr = one*1000+two*100+endThree*10+four
            elif i == 3:
                if four == endFour:
                    continue
                
                newCurr = one*1000+two*100+three*10+ endFour 
            
            
            if (visited[newCurr] == 0 or visited[newCurr] > cnt) and prime[newCurr] == True:
                    visited[newCurr] = cnt
                    dfs(newCurr, end, cnt+1)
    
    for i in range(4): 
        for j in range(0, 10):    
            if i == 0:         
                if j != 0 and j != one:
                    newCurr = j*1000+two*100+three*10+four 
            elif i == 1:
                if j != two:
                    newCurr = one*1000+j*100+three*10+four 
            elif i == 2:
                if j != three:
                    newCurr = one*1000+two*100+j*10+four
            elif i == 3:
                if j != four:
                    newCurr = one*1000+two*100+three*10+j
            
            
            
            if (visited[newCurr] == 0 or visited[newCurr] > cnt) and prime[newCurr] == True:
                    visited[newCurr] = cnt
                    dfs(newCurr, end, cnt+1)
                  
                  
for i in range(T):
    a, b = map(int, input().split())
    
    visited = [0]*10000
    
    minCnt = int(1e9)
    visited[a] = 1
    dfs(a, b, 0)
    
    if minCnt == int(1e9):
        print("impossible")
    else:
        print(minCnt)

 

3. 참고 코드

- BFS를 활용했고, nextNumStr을 numStr을 활용해서 만들고,

  3가지 검사 조건(visited, prime, >=1000)을 추가했다

-> BFS의 최단 거리 개념으로 이해하면 된다 

import math 
from collections import deque 

T = int(input())
prime = [False]*10000
visited = [False]*10000

def isPrime(num):

    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0:
            return False
    return True


for i in range(1000, 10000):
    if isPrime(i) == True:
        prime[i] = True


def bfs(curr, end):
    
    q = deque()
    q.append((curr, 0))
    visited[curr] = True 
    
    minCnt = -1
    
    while q:
        
        num, cnt = q.popleft() 
        
        if num == end:
            minCnt = cnt
            break 
        
        numStr = str(num)
        
        for i in range(4):
            for j in range(10):
                nextNumStr = numStr[:i] + str(j) + numStr[i+1:]
                nextNum = int(nextNumStr)
                
                if visited[nextNum] == False and prime[nextNum] and nextNum>=1000:
                    visited[nextNum] = True
                    q.append((nextNum, cnt+1))
        
    
    
    return minCnt 
    
 

for i in range(T):
    a, b = map(int, input().split())
    
    visited = [0]*10000
    
    ans = bfs(a, b)
    
    if ans == -1:
        print("impossible")
    else:
        print(ans)