오지게 틀렸다.
알파벳 위치를 뽑아내는건 쉬우니깐 넘기자.
피드백 1.
BFS 탐색방법을 잘못 짚었다.
거두절미 하고 소스를 보자.
57줄 ~ 140번째 줄이 중요하다.
|
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
180
181
182
183
|
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#define pii pair<int, int>
using namespace std;
class condi
{
public:
int x;
int y;
int cur_dir;
int left;
};
class first_w
{
public:
int x; int y;
char c;
};
bool comp(const first_w& a, const first_w& b)
{
return a.c < b.c;
}
vector<first_w> nboard;
int check[100];
string ans;
int dx[4] = { 0,0,-1,1 }; // 동서남북
int dy[4] = { 1,-1,0,0 };
void gogo(int m, int n, vector<string> board, string cur)
{
cout << cur << '\n';
if (cur.size() == nboard.size())
{
ans = cur;
return;
}
if (ans != "")
return;
for (int z = 0; z < nboard.size(); z++)
{
if (check[z] != 0)
continue;
int i = nboard[z].x;
int j = nboard[z].y;
char base = nboard[z].c;
int check2[100][100] = { 0 };
check2[i][j] = 1;
queue<condi> q;
for (int k = 0; k < 4; k++)
{
int nx = i;
int ny = j;
while (1)
{
nx += dx[k];
ny += dy[k];
if (nx < 0 || nx >= m || ny < 0 || ny >= n)
break;
if (board[nx][ny] == '.' || board[nx][ny] == base)
{
check2[nx][ny] = 1;
q.push({ nx, ny, k, 1 });
}
else
break;
}
}
while (!q.empty())
{
condi t = q.front();
q.pop();
if (board[t.x][t.y] == base)
{
check[z] = 1;
board[t.x][t.y] = board[i][j] = '.';
gogo(m, n, board, cur + base);
check[z] = 0;
board[t.x][t.y] = board[i][j] = base;
break;
}
for (int k = 0; k < 4; k++)
{
int nx = t.x;
int ny = t.y;
while (1)
{
nx += dx[k];
ny += dy[k];
if (nx < 0 || nx >= m || ny < 0 || ny >= n)
break;
if (k == t.cur_dir) // 방향이 같으면
{
if (board[nx][ny] != '.' && board[nx][ny] != base)
break;
if (check2[nx][ny] == 0)
{
check2[nx][ny] = 1;
q.push({ nx, ny, k, t.left });
}
}
else if (k != t.cur_dir && t.left == 1) // 다르지만 한번까진 꺾기 가능
{
if (board[nx][ny] != '.' && board[nx][ny] != base)
break;
if (check2[nx][ny] == 0)
{
check2[nx][ny] = 1;
q.push({ nx, ny, k, 0 });
}
}
}
}
}
}
}
string solution(int m, int n, vector<string> board)
{
map<char, int> mm;
nboard.clear();
for (int i = 0; i < 100; i++)
check[i] = 0;
ans = "";
for (int i = 0; i < board.size(); i++)
{
for (int j = 0; j < board[i].size(); j++)
{
if (board[i][j] >= 'a' && board[i][j] <= 'z' && mm[board[i][j]] == 0)
{
mm[board[i][j]] = 1;
nboard.push_back({ i,j, board[i][j] });
}
}
}
sort(nboard.begin(), nboard.end(), comp);
gogo(m, n, board, "");
if (ans == "")
return "impossible";
else
return ans;
}
|
cs |
그냥 굉장히 원초적인 BFS를 썻다. 1번까지 방향 전환이 가능하고 그 이후는 같은 방향만 되게
이게 왜 틀렸을까???
현재 요런 map 이 있고 C를 탐색해보자. 위치 구현상
start는 {1,2} 이고 같은 C를 찾으면 된다.
int dx[4], dy[4] 는 동 -> 서 -> 남 -> 북 순서대로다.
틀렸다 그러면 check[100][100][2]를 써서 방향이 전환이 0번 이루어졌다면
check[i][j][1] 에 넣고 방향 전환이 1번 이루어 졌다면 check[i][j][0]으로 넣으면 되지 않아????
이걸로 똑같이 해봐라 안된다. 혼자 해볼때는 확실히 안됐다. 그런데 여기에 쓰기에는 너무 길어져서 귀찮다.
그러면 BFS방법을 어떤것을 써야 하나?????????????????????
6087번: 레이저 통신
크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서
www.acmicpc.net
이 문제를 풀어보면 어떤 방식으로 탐색해야 할지 알 것이다.
풀기 귀찮으면 구글링 해서 어떤 BFS 방식을 쓰는지 알아보는 것도 괜찮다. 근데 한번쯤 풀어보는걸 추천한다.
더보기
각 방향을 기준으로 막힐 때 까지 while()문을 써가면서 1칸씩 계속 전진 해준다.
그래서 바꾸었다.
|
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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#define pii pair<int, int>
using namespace std;
class condi
{
public:
int x;
int y;
int cur_dir;
int left;
};
class first_w
{
public:
int x; int y;
char c;
};
bool comp(const first_w& a, const first_w& b)
{
return a.c < b.c;
}
vector<first_w> nboard;
int check[100];
string ans;
int dx[4] = { 0,0,-1,1 }; // 동서남북
int dy[4] = { 1,-1,0,0 };
char board2[100][100];
void gogo(int m, int n, string cur)
{
//cout << cur << '\n';
if (cur.size() == nboard.size())
{
ans = cur;
return;
}
if (ans != "")
return;
for (int z = 0; z < nboard.size(); z++)
{
if (check[z] != 0)
continue;
int i = nboard[z].x;
int j = nboard[z].y;
char base = nboard[z].c;
int check2[100][100] = { 0 };
check2[i][j] = 1;
queue<condi> q;
for (int k = 0; k < 4; k++)
{
int nx = i;
int ny = j;
while (1)
{
nx += dx[k];
ny += dy[k];
if (nx < 0 || nx >= m || ny < 0 || ny >= n)
break;
if (board2[nx][ny] == '.' || board2[nx][ny] == base)
{
check2[nx][ny] = 1;
q.push({ nx, ny, k, 1 });
}
else
break;
}
}
while (!q.empty())
{
condi t = q.front();
q.pop();
if (board2[t.x][t.y] == base)
{
check[z] = 1;
board2[t.x][t.y] = board2[i][j] = '.';
gogo(m, n, cur + base);
check[z] = 0;
board2[t.x][t.y] = board2[i][j] = base;
break;
}
for (int k = 0; k < 4; k++)
{
int nx = t.x;
int ny = t.y;
while (1)
{
nx += dx[k];
ny += dy[k];
if (nx < 0 || nx >= m || ny < 0 || ny >= n)
break;
if (k == t.cur_dir) // 방향이 같으면
{
if (board2[nx][ny] != '.' && board2[nx][ny] != base)
break;
if (check2[nx][ny] == 0)
{
check2[nx][ny] = 1;
q.push({ nx, ny, k, t.left });
}
}
else if (k != t.cur_dir && t.left == 1) // 다르지만 한번까진 꺾기 가능
{
if (board2[nx][ny] != '.' && board2[nx][ny] != base)
break;
if (check2[nx][ny] == 0)
{
check2[nx][ny] = 1;
q.push({ nx, ny, k, 0 });
}
}
}
}
}
}
}
string solution(int m, int n, vector<string> board)
{
map<char, int> mm;
nboard.clear();
for (int i = 0; i < 100; i++)
check[i] = 0;
ans = "";
for (int i = 0; i < board.size(); i++)
{
for (int j = 0; j < board[i].size(); j++)
{
board2[i][j] = board[i][j];
if (board[i][j] >= 'A' && board[i][j] <= 'Z' && mm[board[i][j]] == 0)
{
mm[board[i][j]] = 1;
nboard.push_back({ i,j, board[i][j] });
}
}
}
sort(nboard.begin(), nboard.end(), comp);
gogo(m, n, "");
if (ans == "")
return "IMPOSSIBLE";
else
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
//int m = 4;
//int n = 4;
//vector<string> board = { "NRYN", "ARYA" };
vector<string> board = { "FGHEI", "BAB..", "D.C*.", "CA..I", "DFHGE" };
//vector<string> board = { "FG...", ".....", "...*.", ".....", ".F.G." };
//vector<string> board = { "...", "D.C", "C.." };
cout << solution(board.size(), board[0].size(), board);
}
|
cs |
하지만 시간 초과가 나버렸다.
피드백 2.
처음에는 알파벳의 순서를 기준으로 빽트래킹 하는 방법을 했었다.
D->F->G->진행이 안돼 G에서 빽
D->F->H->A->I->G-> 진행이 안돼 G에서 빽
D->F->H->A->I->N->B ....
이렇게 전진하다가 안되면 뒤로 빠지는 방법을 택했다.
하지만 이렇게 하면 안좋다.
사천성 게임 특징상 IMPOSSIBLE이 안난다는 기준
특정 문자가 없어진다고 다음 문자를 못 없애는 경우는 없기 때문이다.
즉,
vector<string> board = { "FGHEI", "BAB..", "D.C*.", "CA..I", "DFHGE" };
여기서 I를 먼저 지우던 A를 먼저 지우던 결국 다 지울 수 있다는 것이다.
만약 I를 먼저 지웠을때 IMPOSSIBLE이 나온다면, A를 먼저 지워도 IMPOSSIBLE이 나올 것이다.
그래서 방식을 바꾸었다.
148~162줄이 바뀐 것이 핵심이다.
|
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
|
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#define pii pair<int, int>
using namespace std;
class condi
{
public:
int x;
int y;
int cur_dir;
int left;
};
class first_w
{
public:
int x; int y;
char c;
};
bool comp(const first_w& a, const first_w& b)
{
return a.c < b.c;
}
vector<first_w> nboard;
string ans;
int dx[4] = { 0,0,-1,1 }; // 동서남북
int dy[4] = { 1,-1,0,0 };
char board2[100][100];
bool gogo(int m, int n, int i, int j)
{
char base = board2[i][j];
int check[100][100] = { 0 };
check[i][j] = 1;
queue<condi> q;
for (int k = 0; k < 4; k++)
{
int nx = i;
int ny = j;
while (1)
{
nx += dx[k];
ny += dy[k];
if (board2[nx][ny] == '.' || board2[nx][ny] == base)
{
check[nx][ny] = 1;
q.push({ nx, ny, k, 1 });
}
else
break;
}
}
while (!q.empty())
{
condi t = q.front();
q.pop();
if (board2[t.x][t.y] == base)
{
board2[t.x][t.y] = board2[i][j] = '.';
return true;
}
for (int k = 0; k < 4; k++)
{
int nx = t.x;
int ny = t.y;
while (1)
{
nx += dx[k];
ny += dy[k];
if (nx < 0 || nx >= m || ny < 0 || ny >= n)
break;
if (k == t.cur_dir) // 방향이 같으면
{
if (board2[nx][ny] != '.' && board2[nx][ny] != base)
break;
if (check[nx][ny] == 0)
{
check[nx][ny] = 1;
q.push({ nx, ny, k, t.left });
}
}
else if (k != t.cur_dir && t.left == 1) // 다르지만 한번까진 꺾기 가능
{
if (board2[nx][ny] != '.' && board2[nx][ny] != base)
break;
if (check[nx][ny] == 0)
{
check[nx][ny] = 1;
q.push({ nx, ny, k, 0 });
}
}
}
}
}
return false;
}
string solution(int m, int n, vector<string> board)
{
map<char, int> mm;
nboard.clear();
ans = "";
for (int i = 0; i < board.size(); i++)
{
for (int j = 0; j < board[i].size(); j++)
{
board2[i][j] = board[i][j];
if (board[i][j] >= 'A' && board[i][j] <= 'Z' && mm[board[i][j]] == 0)
{
mm[board[i][j]] = 1;
nboard.push_back({ i,j, board[i][j] });
}
}
}
sort(nboard.begin(), nboard.end(), comp);
bool flag = true;
while (flag)
{
flag = false;
for (int i = 0; i < nboard.size(); i++)
{
flag = gogo(m, n, nboard[i].x, nboard[i].y);
if (flag == true)
{
ans += nboard[i].c;
cout << ans << '\n';
nboard.erase(nboard.begin() + i);
break;
}
}
}
if (nboard.size() != 0)
return "IMPOSSIBLE";
else
return ans;
}
|
cs |
통과는 됐지만
정말 아슬아슬 했다.
그래서 최적화를 고민해봤다.
|
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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
|
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#define pii pair<int, int>
using namespace std;
class condi
{
public:
int x;
int y;
int cur_dir;
int left;
};
class first_w
{
public:
int x; int y;
char c;
};
bool comp(const first_w& a, const first_w& b)
{
return a.c < b.c;
}
vector<first_w> nboard;
string ans;
int dx[4] = { 0,0,-1,1 }; // 동서남북
int dy[4] = { 1,-1,0,0 };
char board2[100][100];
bool gogo(int m, int n, int i, int j)
{
char base = board2[i][j];
int check[100][100] = { 0 };
check[i][j] = 1;
queue<condi> q;
for (int k = 0; k < 4; k++)
{
int nx = i;
int ny = j;
while (1)
{
nx += dx[k];
ny += dy[k];
if (board2[nx][ny] == '.' || board2[nx][ny] == base)
{
if (board2[nx][ny] == base)
{
board2[nx][ny] = board2[i][j] = '.';
return true;
}
check[nx][ny] = 1;
q.push({ nx, ny, k, 1 });
}
else
break;
}
}
while (!q.empty())
{
condi t = q.front();
q.pop();
for (int k = 0; k < 4; k++)
{
int nx = t.x;
int ny = t.y;
while (1)
{
nx += dx[k];
ny += dy[k];
if (nx < 0 || nx >= m || ny < 0 || ny >= n)
break;
if (k == t.cur_dir) // 방향이 같으면
{
if (board2[nx][ny] != '.' && board2[nx][ny] != base)
break;
if (check[nx][ny] == 0)
{
if (board2[nx][ny] == base)
{
board2[nx][ny] = board2[i][j] = '.';
return true;
}
check[nx][ny] = 1;
q.push({ nx, ny, k, t.left });
}
}
else if (k != t.cur_dir && t.left == 1) // 다르지만 한번까진 꺾기 가능
{
if (board2[nx][ny] != '.' && board2[nx][ny] != base)
break;
if (check[nx][ny] == 0)
{
if (board2[nx][ny] == base)
{
board2[nx][ny] = board2[i][j] = '.';
return true;
}
check[nx][ny] = 1;
//q.push({ nx, ny, k, 0 });
}
}
}
}
}
return false;
}
string solution(int m, int n, vector<string> board)
{
map<char, int> mm;
nboard.clear();
ans = "";
for (int i = 0; i < board.size(); i++)
{
for (int j = 0; j < board[i].size(); j++)
{
board2[i][j] = board[i][j];
if (board[i][j] >= 'A' && board[i][j] <= 'Z' && mm[board[i][j]] == 0)
{
mm[board[i][j]] = 1;
nboard.push_back({ i,j, board[i][j] });
}
}
}
sort(nboard.begin(), nboard.end(), comp);
bool flag = true;
while (flag)
{
flag = false;
for(int i = 0 ; i < nboard.size() ; i++)
{
flag = gogo(m, n, nboard[i].x, nboard[i].y);
if (flag == true)
{
ans += nboard[i].c;
cout << ans << '\n';
nboard.erase(nboard.begin() + i);
break;
}
}
}
if (nboard.size() != 0)
return "IMPOSSIBLE";
else
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
//int m = 4;
//int n = 4;
//vector<string> board = { "NRYN", "ARYA" };
vector<string> board = { "FGHEI", "BAB..", "D.C*.", "CA..I", "DFHGE" };
//vector<string> board = { "FG...", ".....", "...*.", ".....", ".F.G." };
//vector<string> board = { "...", "D.C", "C.." };
cout << solution(board.size(), board[0].size(), board);
}
|
cs |
시간이 2400ms 걸린 코드 76~78줄에서 queue에서 받을때 검사하는 것 대신
check와 동시에 검사하는 방법으로 바꾸고 (수정한 코드의 (60~63), (100~103), (117~121))
123번째 줄은 어차피 한번 꺾이고 while로 다 꺾임을 소진했으니깐 빼도 괜찮다라고 생각하에 주석으로 하니
편-안 해졌다.
'뚝배기 터진 문제_programmers' 카테고리의 다른 글
| lv3 블록 이동하기 (0) | 2020.09.12 |
|---|---|
| LV3_보행자 천국 (0) | 2020.09.08 |
| lv3 순위 (0) | 2020.09.06 |
| lv3 자물쇠와 열쇠 (0) | 2020.09.05 |
| lv3 N으로 표현. (0) | 2020.09.05 |