[백준 알고리즘]/[C++]
백준 2210 숫자판 점프 | DFS | C++
말하는펭귄
2021. 3. 12. 10:14
728x90
반응형
이번 포스팅은 백준 2210번 숫자판 점프입니다.
아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.
2210번: 숫자판 점프
111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다.
www.acmicpc.net
기본 알고리즘
DFS (깊이 우선 탐색)
참고
line 46-47 벡터의 중복 원소 제거
C++ vector 중복 원소 삭제
1. unique 함수 unique 함수는 vector에서 중복되지 않는 원소들을 앞에서부터 채워나가는 함수 (algorithm 헤더에 정의) 자신이 바꾼 vector의 end()를 반환 (중복 원소들(쓰레기 값들)의 첫 번째 위치 리턴)
scarlettb.tistory.com
전체 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
//백준2210 숫자판점프
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int map[5][5];
int dy[] = { 0,0,-1,1 };
int dx[] = { -1,1,0,0 };
vector<int> v;
void DFS(int y, int x, int num, int cnt) {
if (cnt == 6) {
v.push_back(num);
return;
}
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= 5 || nx >= 5)
continue;
DFS(ny, nx, num * 10 + map[ny][nx], cnt+1);
}
}
int main() {
/*입력*/
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
cin >> map[i][j];
}
}
/*모든 좌표의 DFS 경로 탐색*/
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
DFS(i, j, 0, 0);
}
}
/*벡터의 중복 원소 제거*/
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
/*정답 출력*/
cout << v.size();
}
|
cs |
728x90
반응형