BOJ 2210 숫자판 점프

https://www.acmicpc.net/problem/2210

2210번: 숫자판 점프

 

0. 문제 개요

숫자판의 임의의 위치에서 출발, 상하좌우로 움직이면서 적혀 있는 숫자들을 뒤에 붙인다. 

이 때 한번 지나간 곳도 다시 지나갈 수 있다. 서로 다른 여섯 자리 숫자의 개수를 구하는 문제.

 

 

1. 문제 해결 아이디어

(1) 자료구조 : 중복되는 경우의 수를 제거해야 하니 set을 이용하자.

(2) bruteforce, 모든 경우의 수를 탐색하자. (숫자판의 사이즈가 5x5 밖에 안 된다.)

 

(1)과 관련하여, string 으로도 set을 구현할 수 있다.

 

한편, string은 vector처럼 한 글자씩 뒤에 push_back 할 수 있다.

 

따라서 string을 하나 선언한뒤,

숫자판을 상하좌우로 이동하면서 string에 한글자씩 뒤에 붙여주고, 길이가 6자리가 되었을 때 string을 set에 넣어준다.

set은 중복을 허용하지 않기 때문에 최종적으로 set의 size가 모든 숫자의 경우의 수가 된다.

다시 말해, 중복 검사를 해줄 필요가 없다!

 

 

2. 코드

#include <iostream>
#include <set>
#include <string>
using namespace std;
 
char m[6][6];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
string str;
set<string> s;
int cnt;
void solve(int x, int y) {
 
    if (str.length() == 6) {            //여섯 자리 숫자가 되면
        s.insert(str);                  //set에 넣어 준다. 중복되는 경우는 알아서 걸러진다.
        return;
    }
    int nx, ny;
    for (int i = 0;i <= 3;i++) {        
        nx = x + dx[i];
        ny = y + dy[i];
        if (1 <= nx && nx <= 5 && 1 <= ny && ny <= 5) {
            str.push_back(m[ny][nx]);
            solve(nx, ny);                //재귀 호출
            str.pop_back();               //한번 방문이 끝나면 탐색이 끝난 것을 string에서 빼준다.(back-tracking)
        }
    }
 
 
}
 
int main() {
 
    for (int i = 1;i <= 5;i++) {
        for (int j = 1;j <= 5;j++) {
            cin >> m[i][j];
        }
    }
    for (int i = 1;i <= 5;i++) {
        for (int j = 1;j <= 5;j++) {
            solve(i, j);
        }
    }
    cout << s.size();                        //set의 size가 곧 모든 숫자의 경우의 수가 된다.
    return 0;
}

 

3. 나가며...

중복되지 않는 경우의 수를 셀 때, set stl이 유용하게 쓰일 수 있다.