1107번 문제풀이 : 완전탐색 알고리즘

1. 문제 분석

문제 한문제 요약

현재 보고 있는 채널(100)에서 목표 채널(N)로 이동하기 위해 고장난 버튼 제외하고 최소 버튼 클릭 횟수를 구하는 문제.

1.2 입출력 조건

입력

• 목표 채널 N (0 <= N <= 500,000)
• 고장 버튼 개수 M (0 <= M <= 10)
• 고장 버튼 목록 (숫자만 해당)

출력

• 목표 채널 N으로 이동하기 위해 최소 버튼 클릭 횟수 출력

---

2. 의사코드

1. 초기 값 설정

   • 현재 채널: 100
   • 최소 클릭 횟수: |N - 100| (즉, +, - 버튼만으로 이동할 때의 횟수)

2. 가능한 모든 채널(0~999999)을 탐색하면서,

   • 숫자 버튼을 눌러 이동할 수 있는 채널을 확인 (고장난 버튼 포함 여부 체크)
   • 해당 채널까지 가는 클릭 횟수 계산 (숫자 입력 횟수 + 추가 이동 횟수)
   • 최소 클릭 횟수 갱신

3. 최소 클릭 횟수를 출력

---

3. 코드

def min_press(N, broken_buttons):
    min_count = abs(N - 100)  # +1, -1 만 사용했을 때 눌러야 하는 버튼
    
    for num in range(1000000):  # 가능한 모든 채널 탐색
        str_num = str(num)
        
        for ch in str_num:  # 각 자릿수가 있는 지 확인
            if int(ch) in broken_buttons:
                break
        else:  # 고장난 버튼이 포함되지 않았다면 실행
            min_count = min(min_count, len(str_num) + abs(num - N)) # 버튼 눌리는 데 부터, N까지 가는 수 
            
    return min_count

# 입력 처리
N = int(input().strip())  # 목표 채널
M = int(input().strip())  # 고장난 버튼 개수
broken_buttons = set(map(int, input().split())) if M else set()

# 최소 버튼 클릭 횟수 출력
print(min_press(N, broken_buttons))

---

4. 이 문제 핵심

4.1 탐색 범위 최적화

• N이 최대 6자리 수이므로, 0부터 999999까지 확인하면 된다.
• 범위가 탐색 가능할 정도이므로 완전 탐색이 가능.

4.2 탐색 가능하다면 1순위는 완전탐색

• N에서 +1, -1 후 가까운 데부터 탐색하려 했으나 실패 (양방향 탐색 방식)
• 완전 탐색이 가능하다면, 먼저 완전 탐색을 시도하는 것이 정답을 보장하여 낫다.