728x90
반응형
https://www.acmicpc.net/problem/5213
5213번: 과외맨
문제 과외맨은 평소에 서강대학교 학생 이민혁으로 위장하고 있는 한국의 대표적인 영웅이다. 그는 슈퍼 히어로가 너무 미국에 집중되어 있는 현실을 안타까워했고, 그의 절친한 친구인 스파이더맨과 아이언맨에게 한국으로 와서 같이 영웅 활동을 하자는 제안을 했으나 거절당했다. 얼마 전, 오랜 잠에서 깨어난 고대 마야인들이 과외맨이 수업을 듣는 동안 과외 노트를 훔쳐갔다. 과외맨은 빼앗긴 노트를 찾아오기 위해 인천 공항으로 가서 과테말라로 가는 비행기를 탔다. 일단
www.acmicpc.net
|
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
#define NSIZE 502
#include<stdio.h>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
struct Data {
int num, idx;
};
struct qData {
int ry, rx, by, bx, cnt;
vector<int>road;
};
Data input[NSIZE][NSIZE * 2];
int chk[NSIZE * NSIZE];
int N;
int dy[] = { 0,0,-1,1 };
int dx[] = { -1,1,0,0 };
/*
00 01 02
10 11 12
*/
int lastNum = 0x80000000;
void init() {
cin >> N;
int cnt = 1;
for (int i = 1; i <= N; i++) {
if (i % 2 == 1) {
for (int j = 1; j <= N * 2; j += 2) {
cin >> input[i][j].num >> input[i][j + 1].num;
input[i][j].idx = input[i][j + 1].idx = cnt++;
}
}
else {
for (int j = 2; j < N * 2; j += 2) {
cin >> input[i][j].num >> input[i][j + 1].num;
input[i][j].idx = input[i][j + 1].idx = cnt++;
}
}
}
}
int maxIdx = 0x80000000;
int cnt = 0;
vector<int>v;
void bfs() {
queue<qData>q;
vector<int>a;
a.push_back(1);
q.push({ 1,1,1,2,1,a });
chk[1] = 1;
while (!q.empty()) {
qData c = q.front(); q.pop();
if (input[c.ry][c.rx].idx == (N * N) - (N / 2)
|| input[c.by][c.bx].idx == (N * N) - (N / 2)) {
cout << c.cnt << endl;
for (int i = 0; i < c.road.size(); i++) {
cout << c.road[i] << " ";
}
cout << endl;
return;
}
for (int dir = 0; dir < 4; dir++) {
qData n;
n.ry = c.ry + dy[dir];
n.rx = c.rx + dx[dir];
n.by = c.by + dy[dir];
n.bx = c.bx + dx[dir];
n.road = c.road;
n.cnt = c.cnt + 1;
if (1 <= n.ry && n.ry <= N * 2 && 1 <= n.rx && n.rx <= N * 2 && 1 <= n.by && n.by <= N * 2 &&
1 <= n.bx && n.bx <= N * 2) { if (dir == 0) {
if (input[n.ry][n.rx].num != 0 && input[n.ry][n.rx].num == input[c.ry][c.rx].num &&
chk[input[n.ry][n.rx].idx] == 0) { chk[input[n.ry][n.rx].idx] = input[c.ry][c.rx].idx;
n.by = n.ry;
n.bx = n.rx;
n.ry = n.ry + dy[dir];
n.rx = n.rx + dx[dir];
n.road.push_back(input[n.ry][n.rx].idx);
if (lastNum < input[n.ry][n.rx].idx)
lastNum = input[n.ry][n.rx].idx;
q.push(n);
}
}
if (dir == 1) {
if (input[n.by][n.bx].num != 0 && input[n.by][n.bx].num == input[c.by][c.bx].num &&
chk[input[n.by][n.bx].idx] == 0) { chk[input[n.by][n.bx].idx] = input[c.by][c.bx].idx;
n.ry = n.by;
n.rx = n.bx;
n.by = n.by + dy[dir];
n.bx = n.bx + dx[dir];
n.road.push_back(input[n.by][n.bx].idx);
if (lastNum < input[n.by][n.bx].idx)
lastNum = input[n.by][n.bx].idx;
q.push(n);
}
}
if (dir == 2) {
if (input[n.ry][n.rx].num != 0 && input[n.ry][n.rx].num == input[c.ry][c.rx].num &&
chk[input[n.ry][n.rx].idx] == 0) { chk[input[n.ry][n.rx].idx] = input[c.ry][c.rx].idx;
int ry = n.ry; int rx = n.rx;
int by = n.by; int bx = n.bx;
by = ry; bx = rx;
ry = ry + dy[0]; rx = rx + dx[0];
if (lastNum < input[by][bx].idx)
lastNum = input[by][bx].idx;
vector<int>nc = n.road;
nc.push_back(input[by][bx].idx);
q.push({ ry,rx,by,bx,n.cnt,nc });
}
if (input[n.by][n.bx].num != 0 && input[n.by][n.bx].num == input[c.by][c.bx].num &&
chk[input[n.by][n.bx].idx] == 0) { chk[input[n.by][n.bx].idx] = input[c.by][c.bx].idx;
int ry = n.ry; int rx = n.rx;
int by = n.by; int bx = n.bx;
ry = by; rx = bx;
by += dy[1]; bx += dx[1];
if (lastNum < input[ry][rx].idx)
lastNum = input[ry][rx].idx;
vector<int>nc = n.road;
nc.push_back(input[ry][rx].idx);
q.push({ ry,rx,by,bx,n.cnt,nc });
}
}
if (dir == 3) {
if (input[n.ry][n.rx].num != 0 && input[n.ry][n.rx].num == input[c.ry][c.rx].num &&
chk[input[n.ry][n.rx].idx] == 0) { chk[input[n.ry][n.rx].idx] = input[c.ry][c.rx].idx;
int ry = n.ry; int rx = n.rx;
int by = n.by; int bx = n.bx;
by = ry; bx = rx;
ry = ry + dy[0]; rx = rx + dx[0];
if (lastNum < input[by][bx].idx)
lastNum = input[by][bx].idx;
vector<int>nc = n.road;
nc.push_back(input[by][bx].idx);
q.push({ ry,rx,by,bx,n.cnt,nc });
}
if (input[n.by][n.bx].num != 0 && input[n.by][n.bx].num == input[c.by][c.bx].num &&
chk[input[n.by][n.bx].idx] == 0) { chk[input[n.by][n.bx].idx] = input[c.by][c.bx].idx;
int ry = n.ry; int rx = n.rx;
int by = n.by; int bx = n.bx;
ry = by; rx = bx;
by += dy[1]; bx += dx[1];
if (lastNum < input[ry][rx].idx)
lastNum = input[ry][rx].idx;
vector<int>nc = n.road;
nc.push_back(input[ry][rx].idx);
q.push({ ry,rx,by,bx,n.cnt,nc });
}
}
}
}
}
vector<int>v;
int cnt = 2;
v.push_back(lastNum);
while (chk[lastNum] != 1) {
cnt++;
v.push_back(chk[lastNum]);
lastNum = chk[lastNum];
}
cout << cnt << endl;
cout << 1 << " ";
for (int i = v.size() - 1; i >= 0; i--) {
cout << v[i] << " ";
}
cout << endl;
}
int main(void) {
init();
bfs();
return 0;
}
|
일단 이문제를 읽어보시면 아시겠지만 정말 앞부분은 영양가 없는 이야기고 그뒤에서 부터 정확히 구현 내용이
나옵니다. 참고해주세요.
이문제는 입력으로 주어지는 숫자 2개가 같은 인덱스를 번호를 가진다고 생각을하고 정말 그림대로 구현을 해주시면
됩니다. 이것이 1단계이고 다른것은 그 인덱스가 같은 번호는 무조건 같이 움직여야한다 빼고 주의 할 만한것은
마지막에 마지막 칸에 도달하지 않는경우가 있으니 그경우 가장 큰값 그러니까 과외맨이 도달할 수 있는 블록 중
가장 큰수 까지의 최단 경로를 출력을 해주시면 됩니다.
제가 앞으로 설명드릴 포인트 대로 bfs 단순 구현해주시면 되기때문에 문제를 풀다가 정말 모르겠다하시면 아래 그림과
첨부되는 내용을 보시고 다시 풀어보시는 것을 추천 드려요.
우선 이렇게 구조체 배열을 만들어주세요. 정말 단순한 구현이기 때문에 다들 금방 하실꺼라 생각합니다.
그리고 가장 포인트는 이동을 어떤식으로 할지 인데
그전에 그 경로를 어떻게 저장해야하나 하시는 분들은 지금까지 풀어온 문제중
DSLR 과 4연산 문제를 아래 첨부해드릴테니 참고하시면 될 것 같습니다. 중요한것은 경로 저장보다는
어떻게 이동 시킬 것인지가 가장 큰 포인트라 생각들기 때문입니다.
2019/09/17 - [알고리즘 (Algorithm)] - 백준 9019 DSLR
백준 9019 DSLR
https://www.acmicpc.net/problem/9019 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를..
3dpit.tistory.com
2019/10/08 - [알고리즘 (Algorithm)] - 백준 14395 4연산
백준 14395 4연산
https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전..
3dpit.tistory.com
이정도 보시면 응용하시는데 문제는 없을꺼라 생각 듭니다.
위의 설명같이 하시면 되고 그래도 나는 이해가 안간다 하시면 그냥 두개 블록을 한번에 같이 이동시키는 bfs를
구현 하는것 이라고 생각하시면 됩니다.
오늘은 여기까지이고 자꾸 업로드가 느려지고 있는데 할것도 많고 아직 밀린것이 좀있어서 조금씩 늦어지네요 무튼
즐거운 코딩하세요.
728x90
반응형
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 2146 다리 만들기 (0) | 2019.10.13 |
|---|---|
| 백준 2151 거울 설치 (0) | 2019.10.11 |
| 백준 3085 사탕게임 (0) | 2019.10.08 |
| 백준 14395 4연산 (0) | 2019.10.08 |
| 백준 9944 NxM 보드 완주하기 (0) | 2019.10.08 |
댓글