Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- DB
- 백준
- 네트워크
- 릿코드
- 응용 계층
- 문제풀이
- 다익스트라
- Transport layer
- Network
- 자료구조
- STL
- Embedded
- 데이터베이스
- ps
- swea
- boot sequence
- Application Layer
- 임베디드
- baekjoon
- 전송 계층
- C++
- 프로그래머스
- BST
- leetcode
- 부트시퀀스
- 관계형 모델
- Djikstra
- dp
- BHS
- Database
Archives
- Today
- Total
BOBO's Note
[ Baekjoon ] 17837. 새로운 게임2 본문
https://www.acmicpc.net/problem/17837
풀이 방법
체스판의 임의의 칸에 여러 개의 말이 쌓여있을 수 있다. 이 정보를 states라는 unordered_map에 저장하도록 한다. key는 칸의 위치를 1차원으로 변환한 값, value는 그 칸에 존재하는 말들의 ID 벡터로 한다. 이때, 해당 벡터를 v라고 하고 크기가 n이라면, v[i]는 v[i+1]~v[n-1]을 업고 있다.
unordered_map< int, vector<int> > states;
white() 함수
이동하려는 칸이 흰색이면 업고 있는 말들을 그대로 업고 이동한다. 우선 states에서 현재 위치에 존재하는 말들 중 자기 자신을 찾고, 그 다음에 존재하는 모든 말들을 stack이라는 벡터에 저장한다. 그 후, 현재 위치에서 이동할 말들을 제거한다.
vector<int> stack;
auto itr = states.find(h.pos);
vector<int>& hlist = itr->second;
n = hlist.size();
for(int i=0; i<n; i++){
if(hlist[i] == h.id){
for(int j=i; j<n; j++){
stack.push_back(hlist[j]);
}
idx = i;
break;
}
}
for(int i=n-1; i>=idx; i--){
hlist.pop_back();
}
새로 이동한 칸에 대해 states 정보를 업데이트한다.
next_pos = next_r * N + next_c;
itr = states.find(next_pos);
if(itr == states.end()){
states.insert(make_pair(next_pos, stack));
for(auto hid: stack){
horses[hid].update(next_r, next_c);
}
}
else{
for(auto hid: stack){
(itr->second).push_back(hid);
horses[hid].update(next_r, next_c);
}
}
red() 함수
이동하려는 칸이 빨간색이면 업고 있는 말들의 순서를 뒤집어 이동한다. 따라서 다음과 같이 stack을 구성한다. 이후 새로 이동한 칸에 대해 states 정보를 업데이트하는 과정은 white() 함수에서와 동일하다.
vector<int> stack;
for(int j=0; j<n; j++){
if(hlist[j] == h.id){
idx = j;
break;
}
}
for(int j=n-1; j>=idx; j--){
stack.push_back(hlist[j]);
hlist.pop_back();
}
이동하려는 칸이 파란색이면 말의 방향을 바꾼 후, 해당 방향으로 한칸 이동하는데 그 칸의 색에 따라 다르게 이동한다.
// revert direction
if(h.dir == RIGHT || h.dir == UP) h.update(h.r, h.c, h.dir+1);
else h.update(h.r, h.c, h.dir-1);
next_r = h.r + dr[h.dir];
next_c = h.c + dc[h.dir];
// move horse
if(valid(next_r, next_c) && board[next_r][next_c] != BLUE){
if(board[next_r][next_c] == WHITE) white(h, next_r, next_c);
else red(h, next_r, next_c);
}
전체 코드는 여기서 확인할 수 있다.
'Algorithm > Problem Solving' 카테고리의 다른 글
[ Baekjoon ] 17070. 파이프 옮기기 1 (0) | 2020.06.02 |
---|---|
[ Baekjoon ] 1920. 수 찾기 (0) | 2020.06.01 |
[ Baekjoon ] 5373. 큐빙 (0) | 2020.05.31 |
[ Baekjoon ] 10217. KCM Travel (0) | 2020.05.28 |
[ Baekjoon ] 1753. 최단 거리 (0) | 2020.05.27 |
Comments