17244번: 아맞다우산
경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출
www.acmicpc.net
알고리즘 종류
- 구현
- BFS
사고 과정
- 이 문제에서 중요한 조건은 재방문 처리이다. 특히 아래와 같은 상황이다. 시작점 S에서 빨간색 선으로 이동하고, 초록색선으로 이동한다. 이 때 초록색 화살표 끝의 X에서는 어떻게 재방문을 처리해야 할까?
- 일단, X를 구별할 수 없으니 번호를 붙여주기로 했다.
- 이제 비교해볼 상황이 있다.
1. 0을 방문했고 다시 0으로 오는 경우
2. 0을 방문했고 1을 방문한 뒤에 다시 0으로 오는 경우
- 위 2가지 경우에서 1번은 재방문을 할 수 없다. 그러나 2번은 재방문을 할 수 있다. 왜냐하면, 위 이미지에서 빨간색과 초록색 경로에 해당하는 경우이기 때문이다. 이런 재방문을 어떻게 처리할 수 있을까? Bit mask를 이용하면 쉽게 해결할 수 있다. 이 문제를 풀어보면 이해하기 쉬울 것이다.
- 2가지 경우를 비트로 나타내보자. 재방문 검사 배열은 isVisited[y][x][1<<X개수]이다.
1. 0을 방문했으면, 1<<0 으로 00001이 된다. 이는 1으로 isVisited[y][x][1] = 1이다. 다시 0을 방문하면 이미 isVisited[y][x][1] = 1이므로 재방문할 수 없다.
2. 0을 방문했으면, 1<<0 으로 00001이 된다. 이어서 1을 방문하면, 1<<1으로 00010이 된다. 둘을 or 연산하면, 00011이 된다. 이는 3으로 isVisited[y][x][3] = 1이 된다. 다시 0을 방문하면, isVisited[y][x][3] = 0이므로 재방문할 수 있다.
- 정리하자면, 비트 마스크를 이용해서 어느 X들을 만나고 왔는지 알 수 있다. 그래서 같은 위치에 오더라도 다른 X를 만나고 왔으면 재방문할 수 있다.
구현(C++)
|
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
|
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
struct State{
int y, x;
int bits=0;
int time=0;
};
int h, w;
int sy, sx;
int totalBits=0;
char mat[51][51];
int isVisited[51][51][1<<6];
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
bool isValid(int y, int x){
return (y>=0 && y<h) && (x>=0 && x<w);
}
void solution(){
queue<State> q; // y, x , X의 bit의 합, 이동 시간
State s;
s.y=sy;
s.x=sx;
q.push(s);
while(!q.empty()){
State cs = q.front();
q.pop();
int cy = cs.y;
int cx = cs.x;
int ct = cs.time;
int cb = cs.bits;
for(int d=0; d<4; d++){
int ny = cy + dir[d][0];
int nx = cx + dir[d][1];
// 모든 물건을 가지고 문에 도착하면 종료
if(mat[ny][nx] == 'E' && cb == totalBits){
cout << ct + 1;
return;
}
if(!isValid(ny, nx)) continue;
// 물건에 도착하면
if(mat[ny][nx] >= '0' && mat[ny][nx] < '5'){
// 같은 물건을 가지고 같은 자리에 왔었는지 확인
int nb = cb | (1 << mat[ny][nx]-'0');
if(!isVisited[ny][nx][nb]){
isVisited[ny][nx][nb] = 1;
State ns;
ns.y = ny;
ns.x = nx;
ns.time = ct + 1;
ns.bits = nb;
q.push(ns);
}
}
// 일반, 출입구, 시작점을 지나는 경우
// 출구가 그래프의 가운데 있을 수도 있어서 지나칠 수 있다.
else if(mat[ny][nx] != '#'){
if(!isVisited[ny][nx][cb]){
isVisited[ny][nx][cb] = 1;
State ns;
ns.y = ny;
ns.x = nx;
ns.time = ct + 1;
ns.bits = cb;
q.push(ns);
}
}
}
}
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> w >> h;
char mark = '0';
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
cin >> mat[i][j];
if(mat[i][j] == 'S'){
sy=i;
sx=j;
mat[i][j] = '.';
}
else if(mat[i][j] == 'X'){
mat[i][j] = mark++; // X에 번호를 붙여준다.
}
}
}
// 모든 X를 더했을 때 최종 값을 구한다.
// X가 3까지면 2^4-1이 최종 값이 된다.
totalBits = (1 << mark-'0') - 1;
solution();
}
|
cs |
시행착오
- 첫 시도는 메모리 초과였다. 본인은 우선순위 큐를 이용해서 X를 방문한 개수 내림차순, 이동시간 오름차순으로 데이터를 저장하여 가장 먼저 X를 방문하면서 최단 시간을 찾으려고 했다. 그런데 재방문 처리를 하지 않았다. 제출에서 50%가 되면서 메모리 초과가 발생했다.
- 배운 것이 있다면, 우선순위 큐에 compare를 만들어서 사용하는 방법이다. 아래에 시도했던 코드가 있다.
|
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
|
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
struct State{
int cnt=0;
int time=0;
int y, x;
string check = "00000";
};
struct cmp{
bool operator()(State a, State b){
if(a.cnt != b.cnt)
return a.cnt < b.cnt;
else
return a.time > b.time;
}
};
int h, w;
int sy, sx, ey, ex;
int thingCnt=0;
int answer=0;
char mat[51][51];
int isVisited[51][51];
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
vector<pair<int, int> > things;
bool isValid(int y, int x){
return (y>=0 && y<h) && (x>=0 && x<w);
}
void solution(){
priority_queue<State, vector<State>, cmp> pq;
State s;
s.y=sy;
s.x=sx;
pq.push(s);
while(!pq.empty()){
State cs = pq.top();
pq.pop();
int cy = cs.y;
int cx = cs.x;
int ct = cs.time;
int cc = cs.cnt;
string cch = cs.check;
for(int d=0; d<4; d++){
int ny = cy + dir[d][0];
int nx = cx + dir[d][1];
if(mat[ny][nx] == 'E' && cc == thingCnt){
answer = ct + 1;
return;
}
if(!isValid(ny, nx)) continue;
if(mat[ny][nx] == '#') continue;
if(mat[ny][nx] >= '0' && mat[ny][nx] < '5'){
int num = mat[ny][nx] - '0';
if(cs.check[num] == '0'){
State ns;
ns.y = ny;
ns.x = nx;
ns.cnt = cc + 1;
ns.time = ct + 1;
ns.check = cch;
ns.check[num] = '1';
pq.push(ns);
}
else{
State ns;
ns.y = ny;
ns.x = nx;
ns.cnt = cc;
ns.time = ct + 1;
ns.check = cch;
pq.push(ns);
}
}
else{
State ns;
ns.y = ny;
ns.x = nx;
ns.cnt = cc;
ns.time = ct + 1;
ns.check = cch;
pq.push(ns);
}
}
}
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> w >> h;
int mark = '0';
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
cin >> mat[i][j];
if(mat[i][j] == 'S'){
sy=i;
sx=j;
mat[i][j] = '.';
}
else if(mat[i][j] == 'E'){
ey=i;
ex=j;
}
else if(mat[i][j] == 'X'){
things.push_back({i,j});
mat[i][j] = mark;
mark++;
thingCnt++;
}
}
}
solution();
cout << answer << endl;
}
|
cs |
- 골드 3이상이 되면서 재방문 조건이 까다로워 지고 있다. 이번 문제에서는 비트 마스크를 이용한 재방문 조건 생성이다. A지점을 방문할 때, A에서 A로 오는 재방문은 방지 하지만, A에서 B를 갔다가 다시 A로 오는 재방문은 허락한다.
'코딩 공부 > 백준' 카테고리의 다른 글
| [백준][C++] 2533 사회망 서비스(SNS) (2) | 2021.03.31 |
|---|---|
| [백준][C++] 2250 트리의 높이와 너비 (0) | 2021.03.31 |
| [백준][C++] 1766 문제집 (0) | 2021.03.30 |
| [백준][C++] 1715 카드 정렬하기 (0) | 2021.03.29 |
| [백준][C++] 1400 화물차 (0) | 2021.03.27 |