문제 출처: https://www.acmicpc.net/problem/14503
풀이
최초의 로봇청소기의 좌표로부터 4방향을 검색하면서 방향을 바꾸는 연산이 너무 까다로웠습니다..
로봇 청소기의 좌표 및, 방향을 담을 수 있는 큐를 선언하여 bfs를 이용했습니다.
현재 자리에서 왼쪽부터 탐색하여 벽이있거나, 이미 청소했을 경우, 방향을 그 쪽으로 돌리는게 핵심이었습니다.
문제에서 주어진대로 0번 인덱스:북, 1번: 동, 2번 : 남, 3번 서 쪽으로 각각 지정해서 dx[4],dy[4] 좌표를 선언했습니다.
bfs 수행중에 중요한것은, 네 방향을 방향 순서에 따라 탐색 중, 청소할 수 있는 좌표를 만나면 좌표를 남기고 탈출해야합니다.(4번연산하지않게)
왼쪽부터 탐색하여 향하는 방향을 갱신해주는 연산 코드는 아래와 같습니다. (이게 너무 어려웠습니다.) 매번 향하는 순서가 규칙적이므로, 아래 코드가 성립합니다.
int next_go = (go + (3 - i)) % 4;
그리고 두번 쨰로 까다로운 연산은 후진 할 떄, 방향은 유지하며 후진하는 것입니다. 그런데 사실 까다로운건 없습니다. 아래와 같이 작성하면 이게 곧 그 뜻이됩니다.
int by = y - dy[go];
int bx = x - dx[go];
이렇게 식을 세울줄 알면 끝이라서,, 나머지설명은 주석으로 확인해주세요.
코드
#include<iostream> #include<queue> using namespace std; int map[50][50]; int dy[4] = { -1,0,1,0 }; int dx[4] = { 0,1,0,-1 }; int n, m, r, c, d, room; queue<pair<pair<int, int>,int>> q; void bfs(); int main() { cin >> n >> m >> r >> c >> d; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> map[i][j]; bfs(); cout << room; } void bfs() { q.push({ {r,c},d }); while (!q.empty()) { int y = q.front().first.first; int x = q.front().first.second; int go = q.front().second; if (map[y][x] == 0) { room++; map[y][x] = 10; } q.pop(); bool check = false; for (int i = 0; i < 4; i++) { //좌표의변화. 이게 너무어려웠음 int next_go = (go + (3 - i)) % 4; int ny = y + dy[next_go]; int nx = x + dx[next_go]; //(1,0)인상태) if (nx >= 0 && ny >= 0 && nx < m && ny < n) { if (map[ny][nx] == 0) { q.push({ {ny,nx},next_go }); check = true; break; } } } //네 방향 모두 청소되어있을떄 || 네방향모두 벽일 때 if (!check) { //방향을 유지하며 한칸 후진. int by = y - dy[go]; int bx = x - dx[go]; //후진할 수 있으면 후진해서 다시 시작 if ((0 <= by && by < n && 0 <= bx && bx < m) && map[by][bx] != 1) q.push({ {by, bx}, go }); //후진할 수 없으면 종료 else break; } //빈칸을 찾아서 청소하러 이동한경우 skip else continue; } }
결과
'문제풀이(BOJ) > 삼성 sw역량테스트 기출' 카테고리의 다른 글
| [백준 17144] 미세먼지 안녕! (0) | 2020.01.29 |
|---|---|
| [백준 3190] 뱀 (0) | 2020.01.29 |
| [백준 14501] 퇴사 (0) | 2020.01.27 |
| [백준 14499] 주사위 굴리기 (0) | 2020.01.27 |
| [백준 13458] 시험 감독 (0) | 2020.01.27 |
