[백준온라인] 33702번 비밀번호

백준 33702번 - 비밀번호 🔐

🔗 문제 링크: https://www.acmicpc.net/problem/33702

33702번: 비밀번호

 

---

📝 문제 요약

3×3 키패드가 주어지고, 첫 입력값으로 시작할 숫자 K가 주어진다.
비밀번호를 입력할 때는 바로 직전에 누른 버튼과 상하좌우로 인접한 버튼만 누를 수 있다.
이 규칙을 지키며 생성할 수 있는 가능한 비밀번호 개수를 구하는 문제이다.

---

🧷 문제 분류

수학

---

📦 제출 정보

🔗 소스코드: GitHub - cbkpar/BOJ/boj_33702.cpp

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
93802579	cbkpar	33702	맞았습니다!!	2020 KB	0 ms	C++17	281 B

---

💻 코드 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int iK;
    cin >> iK;

    if (iK % 2 == 0)
    {
        cout << "0" << "\n";
    }
    else
    {
        cout << "8" << "\n";
    }

    return 0;
}

---

💡 풀이 방법

• 중복 없이 모든 가능한 경로 탐색
• 방문 체크를 통해 한 경로 내에서 같은 숫자를 반복 사용하지 않도록 처리
• DFS를 사용한 정석적인 방법도 있지만, 위치별 특성을 고려해 단순하게 계산할 수도 있다

🔢 숫자별 시작 위치에 따른 경로 수 분석

1로 시작했을 때

• 2로 가는 경우 총 4가지
  • 경로 예시: 1→2→3→6→5→4→7→8→9
  • 예시 경로들: 123654789, 123698745, 123698547, 125478963
• 4로 가는 경우도 동일하게 4가지
• 총 8가지 경로 가능
• ※ 3, 7, 9도 1처럼 구석(코너)이기 때문에 동일하게 8가지 가능

2로 시작했을 때

• 1 또는 3으로 가는 경우, 나머지를 모두 채우면 다시 돌아올 수 없음
• 5로 가는 경우도 1 또는 3을 다시 방문해야 하므로 실패
• 총 0가지

5로 시작했을 때

• 상하좌우(2, 4, 6, 8)로 이동 가능
• 시계방향 또는 반시계방향으로 한 바퀴 도는 경로가 존재
• 총 8가지

---

🧪 예제 입력 / 출력

📘 예제 1

입력

3

출력

8

 

📙 예제 2

입력

8

출력

0