https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
<풀이>
1. 입력받은 4X4 배열에서 한 칸씩 시작한다.
2. 각 칸에서 갈 수 있는 4방향으로 계속 가면서 7자리의 숫자를 만든다.
3. 모든 칸에서의 탐색을 끝내고 결과를 출력한다.
<해법>
1. 7자리 숫자를 만드는 방법.
=> 이 문제를 처음에 만들어지는 수를 string으로 접근하였는데 시간 초과가 해결되지 않았습니다. 그래서 int로 접근하였습니다.
|
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
struct pos {
int x, y;
};
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
int map[4][4];
bool words[10000000];
int res;
bool inner(int x, int y) {
if (x < 0 || y < 0 || x >= 4 || y >= 4) {
return false;
}
return true;
}
void go(pos cur, int word, int moveCnt) {
//숫자 7개 완성 - 종료
if (moveCnt == 7) {
words[word] = true;
return;
}
//기존 단어에 10을 곱해 한 자릿수 올려주고, 현재 좌표 값 더하기
word *= 10;
word += map[cur.x][cur.y];
//4방향 중 갈 수 있는 곳으로 탐색
for (int i = 0; i < 4; i++) {
pos nxt = cur;
nxt.x += di[i];
nxt.y += dj[i];
if (!inner(nxt.x, nxt.y)) {
continue;
}
go(nxt, word, moveCnt + 1);
}
}
int main() {
int test_case;
int T;
cin >> T;
for (test_case = 1; test_case <= T; test_case++) {
//사용할 변수 초기화
memset(words, false, sizeof(words));
res = 0;
//입력
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cin >> map[i][j];
}
}
//각 칸마다 재귀함수
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
pos str = { i,j };
go(str, 0, 0);
}
}
//결과 카운트 및 출력
int res = 0;
for (int i = 0; i < 10000000; i++) {
if (words[i]) {
res++;
}
}
cout << "#" << test_case << " " << res << "\n";
}
return 0;
}
|
재귀함수에 대해 알아볼 수 있는 문제였습니다.
'알고리즘 문제풀이 > SWEA' 카테고리의 다른 글
| [C++] SWEA 2383 - 점심 식사시간 (0) | 2020.05.03 |
|---|---|
| [C++] SWEA 2382 - 미생물 격리 (0) | 2020.05.03 |
| [C++] SWEA 1240 - 단순 2진 암호코드 (0) | 2020.05.03 |
| [C++] SWEA 1961 - 숫자 배열 회전 (0) | 2020.05.03 |
| [C++] SWEA 1206 - View (0) | 2020.05.03 |
