SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
<풀이>
1. 방 정보를 입력받는다.
2. 방을 최대로 이동할 수 있을 때의 방 숫자와, 그 때 이동한 방 개수를 출력한다.
<해법>
1. 이동한 방 개수를 구하는 방법
=> 이동한 방 개수를 구하는 방법은 굉장히 간단합니다. 각 좌표마다 방을 이동할 수 있을때까지 이동하고, 총 개수를 구합니다. 하지만 여기서 조금 더 생각하면 중복을 제거할 수 있는 원리가 보입니다.
위 그림과 같이 4번 방에서 이동할 수 있는 방의 개수는 (1+3번 방에서 이동할 수 있는 방의 개수) 입니다.
따라서, 위 점화식을 사용하여 DP로 접근하면 중복을 제거할 수 있습니다.
|
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
//구조체 : 좌표
struct pos {
int x, y;
};
//4방향 : 북, 동, 남, 서
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
int map[1000][1000];
int cache[1000][1000]; //DP 저장 배열
int N;
int Answer_RoomNum;
int Answer_RoomCnt;
//현재 좌표가 범위 안에 있는지 판단
bool isInner(pos p) {
if (p.x < 0 || p.y < 0 || p.x >= N || p.y >= N) {
return false;
}
return true;
}
//현재 좌표에서 다음 좌표로 이동할 수 있는지 판단
bool canGo(pos cur, pos nxt) {
if (map[cur.x][cur.y] + 1 == map[nxt.x][nxt.y]) {
return true;
}
return false;
}
//DP 풀이
int move(pos cur) {
int& ret = cache[cur.x][cur.y];
if (ret != -1) {
return ret;
}
ret = 1;
for (int i = 0; i < 4; i++) {
pos nxt = cur;
nxt.x += di[i];
nxt.y += dj[i];
if (!isInner(nxt)) {
continue;
}
if (canGo(cur, nxt)) {
/*
현재 좌표에서 이동할 수 있는 방의 수 = 1 + 다음 좌표에서 이동할 수 있는 방의 수
*/
ret += move(nxt);
}
}
return ret;
}
int main() {
int test_case;
int T;
cin >> T;
for (test_case = 1; test_case <= T; test_case++) {
//초기화
memset(map, 0, sizeof(map));
memset(cache, -1, sizeof(cache));
N = 0;
Answer_RoomNum = 0, Answer_RoomCnt = 0;
//입력
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
}
}
//해법
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
//{i, j}에서 이동할 수 있는 방의 개수 구하기
int Tmp_RoomCnt = move({ i, j });
//결과 갱신
if (Tmp_RoomCnt > Answer_RoomCnt) {
Answer_RoomCnt = Tmp_RoomCnt;
Answer_RoomNum = map[i][j];
}
else if (Tmp_RoomCnt == Answer_RoomCnt) {
Answer_RoomNum = min(Answer_RoomNum, map[i][j]);
}
}
}
//결과 출력
cout << "#" << test_case << " " << Answer_RoomNum << " " << Answer_RoomCnt << "\n";
}
//종료
return 0;
}
|
DP에 대해 알아볼 수 있는 문제였습니다.
'알고리즘 문제풀이 > SWEA' 카테고리의 다른 글
| [C++] SWEA 2115 - 벌꿀채취 (0) | 2022.11.28 |
|---|---|
| [C++] SWEA 1486 - 장훈이의 높은 선반 (0) | 2021.01.21 |
| [C++] SWEA 4408 - 자기 방으로 돌아가기 (0) | 2021.01.17 |
| [C++] SWEA 3752 - 가능한 시험 점수 (0) | 2021.01.13 |
| [C++] SWEA 2814 - 최장 경로 (0) | 2021.01.12 |