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
- BFS
- 시뮬레이션
- Team Fortress 2
- 스택
- 유니티
- 알고리즘
- 정렬
- 투 포인터
- 백준
- 우선순위 큐
- 그리디 알고리즘
- ue5
- 누적 합
- c++
- 백트래킹
- 다익스트라
- 브루트포스
- 다이나믹 프로그래밍
- Unreal Engine 5
- 자료구조
- 수학
- XR Interaction Toolkit
- 그래프
- 트리
- 재귀
- 구현
- 유니온 파인드
- VR
- 문자열
- DFS
Archives
- Today
- Total
1일1알
백준 14503번 로봇 청소기 C++ 본문

방향에 따라 회전하는 것을 잘 구현하는 게 이 문제의 핵심인 것 같다.
위, 오른쪽, 아래, 왼쪽을 바라보는 것이 순서대로 0, 1, 2, 3 이기 때문에 다음 위치를 계산할 수 있게 해주는 배열을
왼쪽, 위, 오른쪽, 아래 순으로 만들었다. 현재 방향이 위쪽, 즉 0이라면 (r + posR[0] , r + posC[0]) 을 해주면 현재 위치와 방향을 기준으로 해서 왼쪽 좌표를 구할 수 있다.
그리고 문제에서 1번, 2번 행동이 나뉘어져 있기 때문에 함수에서도 매개변수로 step을 받아서 그에 맞는 코드를 실행시키도록 만들었다.
2번의 a에서 위의 식을 이용하면 왼쪽 좌표를 구할 수 있다. 그리고 왼쪽으로 방향도 돌려야 하는데, 하나씩 써보면서 하면 방법을 생각하기 쉽다. 0 -> 3, 1 -> 0, 2 -> 1, 3 -> 2 로 방향이 바뀌어야 하기 때문에 (d+3) % 4를 해주면 된다.
2번의 b에서는 회전만 시켜주고 주변의 청소할 수 없는 좌표의 수를 저장하는 cnt를 1 증가시킨다.
2번의 b가 계속되면서 cnt가 4가 됐을때는 4방향 모두 청소를 할 수 없는 상태이기 때문에 현재 좌표의 뒤를 검사해서 갈 수 있다면 후진하고, 갈 수 없다면 함수를 종료한다.
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
int posR[4] = { 0,-1,0,1 };
int posC[4] = { -1,0,1,0 };
int n, m;
int r, c, d;
vector<vector<int>> v(50, vector<int>(50));
int ans = 0;
void Clean(int step, int cnt) {
if (step == 1) {
v[r][c] = 2;
ans++;
Clean(2, 0);
}
else if (step == 2) {
int leftRow = r + posR[d];
int leftCol = c + posC[d];
if (v[leftRow][leftCol] == 0) {
d = (d + 3) % 4;
r = leftRow;
c = leftCol;
Clean(1, 0);
}
else {
if (cnt < 4) {
d = (d + 3) % 4;
Clean(2, cnt + 1);
}
else {
int backRow = r + posR[(d + 3) % 4];
int backCol = c + posC[(d + 3) % 4];
if (v[backRow][backCol] == 2) {
r = backRow;
c = backCol;
Clean(2, 0);
}
else {
return;
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
cin >> r >> c >> d;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> v[i][j];
}
}
Clean(1, 0);
cout << ans;
};
'알고리즘' 카테고리의 다른 글
백준 3190번 뱀 C++ (0) | 2022.01.01 |
---|---|
백준 15686번 치킨 배달 C++ (0) | 2021.12.31 |
백준 7562번 나이트의 이동 C++ (0) | 2021.12.29 |
백준 14502번 연구소 C++ (0) | 2021.12.28 |
백준 1500 최대 곱 C++ (0) | 2021.12.27 |