백준 33702 (C++) 비밀번호

최초 업로드: 2025-04-09 13:31:22

최근 수정 시간: 2025-07-25 10:01:36

게시자: rlatjwls3333

카테고리: 백준

# [Bronze II] 비밀번호

[문제 링크](https://www.acmicpc.net/problem/33702)

## 문제 설명

<p>쿠는 $9$자리 비밀번호를 정하려고 한다. 비밀번호 버튼은 아래와 같이 생겼다.</p>

<p>쿠가 만들고 싶은 비밀번호의 조건은 아래와 같다.</p>

<ul>
	<li>가장 먼저 $K$가 적힌 버튼을 눌러야 한다.</li>
	<li>이후 직전에 누른 버튼과 상하좌우로 인접한 버튼을 눌러야 한다.</li>
	<li>각 버튼을 한 번씩만 눌러야 하며, 모든 버튼을 눌러야 한다.</li>
</ul>

<p>$K$가 적힌 버튼에서 비밀번호를 누르기 시작할 때 만들 수 있는 서로 다른 비밀번호의 개수를 구해보자.</p>

## 입력

<p>쿠가 비밀번호를 가장 먼저 누르는 버튼에 적힌 수 $K$가 주어진다. $left(1 leq K leq 9
ight)$</p>

## 출력

<p>$K$가 적힌 버튼에서 비밀번호를 누르기 시작할 때, 만들 수 있는 서로 다른 비밀번호의 개수를 출력한다.</p>

## 풀이
#### 종류가 가장자리의 모서리(1), 가장자리의 면(2), 가운데(5) 총 3가지여서 if문으로 문제를 풀 수 있습니다.
#### 그리고 depth가 최대 8까지 내려가는 백트래킹 알고리즘으로 직접 경로를 찾아볼 수 있습니다. 아래 코드는 백트래킹으로 풀었습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int cnt;
bool visited[3][3];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void back(int depth, int x, int y) {
    if(depth==8) {
        cnt++;
        return;
    }

visited[x][y]=true;
    for(int i=0;i<4;i++) {
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx<0 || nx>=3 || ny<0 || ny>=3 || visited[nx][ny]) continue;
        back(depth+1, nx, ny);
    }
    visited[x][y]=false;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int k; cin >> k;
    back(0, (k-1)/3, (k-1)%3);
    cout << cnt;
}
```