BOJ 14503 : 로봇 청소기 - C++
로봇 청소기
코드
#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#define ll long long
#define ull unsigned long long
using namespace std;
// 07:44 ~ 09:37
int dx[4] = {0, 1, 0, -1}; // 북, 동, 남, 서 (dir감소 -> 왼쪽 회전)
int dy[4] = {-1, 0, 1, 0};
int N, M, ans=1, D;
int y, x;
int board[52][52];
bool vis[52][52];
void left(){
D--;
if(D<0) D+=4;
}
int reverse(){
int newD = D;
newD +=2;
if(newD>3) newD -=4;
return newD;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
cin >> y >> x >> D;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
cin >> board[i][j];
vis[y][x] = true;
board[y][x] = 2;
int reverseCnt = 0;
while(true)
{
int tD = D-1;
if(tD<0) tD+=4;
int ny = y + dy[tD]; // 실제 검사는 왼쪽을 하기 때문에 D-1이 필요
int nx = x + dx[tD];
/* 방향전환을 4번해서 후진해야 하는 경우 */
if(reverseCnt == 4){
int nD = reverse();
int nny = y + dy[nD];
int nnx = x + dx[nD];
if(board[nny][nnx] == 1) goto stop;
if(!vis[nny][nnx]){
vis[nny][nnx] = true;
board[nny][nnx] = ++ans;
reverseCnt = 0;
}
y = nny;
x = nnx;
reverseCnt = 0;
continue;
}
/* 벽이면 방향 전환 */
if(board[ny][nx] == 1 or vis[ny][nx] == true){
left();
reverseCnt++;
continue;
}
/* 이동해서 청소할 수 있는 경우 */
vis[ny][nx] = true;
board[ny][nx] = ++ans;
reverseCnt = 0;
left();
y = ny;
x = nx;
}
stop:;
cout << ans;
return 0;
}
- 로직
현재 방향(북, 동, 남, 서)
에 맞춰 dx[] / dy[]
설정
현재 방향을 기준
으로 왼쪽 방향
을 임시 방향
tD
로 두고 검사할 좌표
를 표시 (ny, nx)
벽
이라면 dir을 감소
시켜서 왼쪽으로 전환
/ 동시에 후진을 위한
reverseCnt++
reverseCnt
가 4
라면 후진 한번 한 뒤
다시 4방향을 검사
후진을 할 수 없는 상황
이라면 종료
- 문제 이해
청소한 자리
로 후진할 수 없다고 이해
해서 문제 풀이가 오래 걸림
--> 벽
일 경우에만 종료
이고, 청소한 자리
라면 후진
하여 4방향
을 다시 검사
할 수 있음
Test Case 2번
의 움직임
은 다음과 같다
- 느낀 점
: 시뮬레이션 문제
는 문제에 대한 이해
가 어려운 경우
가 있어서 확실히 하고 넘어가야 할 듯
Author And Source
이 문제에 관하여(BOJ 14503 : 로봇 청소기 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-14503-로봇-청소기-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include <cstdio> #include <vector> #include <queue> #include <iostream> #include <cmath> #include <algorithm> #include <set> #include <deque> #include <numeric> #define ll long long #define ull unsigned long long using namespace std; // 07:44 ~ 09:37 int dx[4] = {0, 1, 0, -1}; // 북, 동, 남, 서 (dir감소 -> 왼쪽 회전) int dy[4] = {-1, 0, 1, 0}; int N, M, ans=1, D; int y, x; int board[52][52]; bool vis[52][52]; void left(){ D--; if(D<0) D+=4; } int reverse(){ int newD = D; newD +=2; if(newD>3) newD -=4; return newD; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> M; cin >> y >> x >> D; for(int i=0;i<N;i++) for(int j=0;j<M;j++) cin >> board[i][j]; vis[y][x] = true; board[y][x] = 2; int reverseCnt = 0; while(true) { int tD = D-1; if(tD<0) tD+=4; int ny = y + dy[tD]; // 실제 검사는 왼쪽을 하기 때문에 D-1이 필요 int nx = x + dx[tD]; /* 방향전환을 4번해서 후진해야 하는 경우 */ if(reverseCnt == 4){ int nD = reverse(); int nny = y + dy[nD]; int nnx = x + dx[nD]; if(board[nny][nnx] == 1) goto stop; if(!vis[nny][nnx]){ vis[nny][nnx] = true; board[nny][nnx] = ++ans; reverseCnt = 0; } y = nny; x = nnx; reverseCnt = 0; continue; } /* 벽이면 방향 전환 */ if(board[ny][nx] == 1 or vis[ny][nx] == true){ left(); reverseCnt++; continue; } /* 이동해서 청소할 수 있는 경우 */ vis[ny][nx] = true; board[ny][nx] = ++ans; reverseCnt = 0; left(); y = ny; x = nx; } stop:; cout << ans; return 0; }
- 로직
현재 방향(북, 동, 남, 서)
에 맞춰dx[] / dy[]
설정현재 방향을 기준
으로왼쪽 방향
을임시 방향
tD
로 두고검사할 좌표
를 표시(ny, nx)
벽
이라면dir을 감소
시켜서왼쪽으로 전환
/ 동시에후진을 위한
reverseCnt++
reverseCnt
가4
라면후진 한번 한 뒤
다시4방향을 검사
후진을 할 수 없는 상황
이라면종료
- 문제 이해
청소한 자리
로후진할 수 없다고 이해
해서 문제 풀이가오래 걸림
-->벽
일 경우에만종료
이고,청소한 자리
라면후진
하여4방향
을다시 검사
할 수 있음Test Case 2번
의움직임
은 다음과 같다
- 느낀 점
:시뮬레이션 문제
는문제에 대한 이해
가어려운 경우
가 있어서확실히 하고 넘어가야 할 듯
Author And Source
이 문제에 관하여(BOJ 14503 : 로봇 청소기 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-14503-로봇-청소기-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)