프로그래머스 단어변환 & 백준 1963 소수경로 (DFS/BFS) 유사문제 정리

https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

 

핵심 알고리즘 

- 단어에서 알파벳은 하나씩만 바꿀 수 있으므로, begin 단어의 길이가 n이라고 했을 때 현재 확인하는 단어의 동일한 알파벳이 n-1 개 인지 체크해야 한다 
- bfs 를 이용해서 풀면 최소 단계를 카운트 하기 편하다 !! queue에 step 을 저장하고 새로 업데이트 될때마다 step+1 해주면된다. 

from collections import deque 

def solution(begin, target, words):
    answer = 0
    if target in words:
        # bfs 실행 
        queue = deque()
        queue.append((begin, 0)) 
        n = len(begin) # 단어의 길이 
        visited = [False] * len(words) # 방문 여부 표시하기 
        
        while queue:
            now, step = queue.popleft()
            if now == target:
                return step 
            for i in range(len(words)):
                if visited[i] == False: # 아직 방문하지 않은 경우 
                    count = 0 
                    for j in range(n): # 글자 하나씩 체크 
                        if now[j] == words[i][j]:
                            count += 1
                        if count >= n-1: 
                            visited[i] = True 
                            queue.append((words[i], step+1))
    else:
        return answer

 

마침 우연히도 어제 백준에서 비슷한 문제를 풀었는데, 소수경로라는 문제이다 
핵심적인 bfs알고리즘은 동일한데 다른점은 bfs 로 최소 단계를 찾기 이전에 소수를 걸러놓는 작업을 해야 한다는 것이다 
 
https://www.acmicpc.net/problem/1963

1963번: 소수 경로

 

에라토스테네스의 체 알고리즘 code snippet :
https://sinclairstudio.tistory.com/165

[Python] 소수판별 알고리즘/에라토스테네스의 체

주의할 점은 처음에 무식하게 for 문을 2부터 10000까지 돌렸는데, 이는 시간낭비.. 시간초과를 불러일으킨다. 
100*100 = 10000 즉 제곱수까지만 확인하게 하여 효율적으로 개선할 수 있다. 
실제로 시간초과 떴음;;

# https://www.acmicpc.net/problem/1963
from collections import deque
import sys
# 에라토스테네의 체 -> 소수 판별
array = [True] * 10000

for x in range(2, 100):
    if array[x]:
        y = 2
        for y in range(x*2, 10000, x):
            array[y] = False

def solve(a, b):
    queue = deque()
    queue.append((a, 0)) # (현재 비밀번호, count)
    visited = [False] * 10000 # 1000 ~ 9999 표시
    visited[a] = True
    while queue:
        num, count = queue.popleft()
        if num == b:
            return count # result
        if num < 1000: # 네자리수 이하 안됨
            continue
        # 한자리씩 바꿔보면서 소수이면서 not visited한 것 큐에 append
        str_num = str(num)
        for i in range(4):
            for j in range(10): # 0 ~ 9
                temp = int(str_num[:i] + str(j) + str_num[i+1:])
                if visited[temp] == False and array[temp] == True:
                    visited[temp] = True
                    queue.append((temp, count+1))

t = int(sys.stdin.readline())
for _ in range(t):
    a, b = map(int, sys.stdin.readline().split())
    result = solve(a, b)
    if result != None:
        print(result)
    else:
        print("Impossible")

아 역시 파이썬;; 이다 싶은건 문자열 슬라이싱.. 진짜 편하다 ㅎ

숫자를 문자열로 바꾼다음에 
일/십/백/천 자리 하나씩 숫자 0~9 로 바꿔본다 (brute force) 
바꾼 문자열을 다시 int 타입으로 변환한다 -> 이게 temp 변수이다. 
새로운 숫자 조합이 소수에 해당되는지 확인한다. -> array[temp] == True // 소수 판별 알고리즘에서 true 로 남은 숫자들은 소수에 해당