📌 참고
교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏
💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers
교공 알고리즘 스터디 21주차 삼성기출
문제풀이 (2022-01-27 THU 💻)
🤔 사담
처음에 문제 이해하는데 시간이 조금 걸리긴 했지만
조건 이해한 후에 순수 코딩하는 시간으로만은
그동안 풀었던 구현 문제 중에서 그나마 제일 금방 풀었던 문제였다
⭐ 풀이의 핵심
문제를 이해하는 데는 아래 블로그의 그림을 참고하였다
cf) https://royhelen.tistory.com/14
재귀 호출 을 활용하여 풀었고
clean이라는 함수와 checkBack이라는 함수 두 가지를 만들었다
- clean 함수에서 문제의 1, 2-a, 2-b 조건을 수행하고 cleanAble이라는 bool 타입 변수를 통해 해당 변수의 값이 false일 경우 즉, 네 방향 모두 청소가 이미 되었거나 벽인 경우 checkBack 함수 호출
- checkBack 함수에서 후진할 수 있는지 확인 후 clean 함수로 돌아감
- 후진이 불가능할 경우 return false
- 또는 후진이 가능할 경우 후진한 후 return true
- clean 함수로 돌아와 checkBack 함수의 return 값에 따라
- true일 경우 clean 함수를 재귀 호출하여 청소 계속
- 또는 false일 경우 clean 함수 종료
🔽 코드 (C++)
#include <iostream>
#include <vector>
using namespace std;
#define NORTH 0
#define EAST 1
#define SOUTH 2
#define WEST 3
// 0:NORTH↑ 1:EAST→ 2:SOUTH↓ 3:WEST←
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
// 세로 크기 N과 가로 크기 M
int N, M;
// 로봇청소기가 있는 칸의 좌표 (r,c)와 바라보는 방향 d
struct Robot {
int r, c, d;
};
Robot robot;
int answer = 0;
bool checkBack(vector<vector<int>> map) {
// 후진 방향 설정
int backD;
if (robot.d == NORTH || robot.d == SOUTH) {
backD = 2-robot.d; // 0:NORTH <-> 2:SOUTH
}
else { // robot.d == EAST || robot.d == WEST
backD = 4-robot.d; // 1:EAST <-> 3:WEST
}
int backR = robot.r + dr[backD];
int backC = robot.c + dc[backD];
// 후진 가능 여부 체크
// d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
if (map[backR][backC] == 1) { // 후진 불가능 (종료)
return false;
}
// c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
else { // 후진 가능 (후진 실시)
robot.r = backR;
robot.c = backC;
return true;
}
}
void clean(vector<vector<int>> &map) {
// 1. 현재 위치를 청소한다.
if (map[robot.r][robot.c] == 0) {
map[robot.r][robot.c] = -1; // 청소 완료 칸은 -1로 표시
answer++;
}
int nextD = robot.d;
int nextR, nextC;
bool cleanAble = false;
for (int i=0; i<4; i++) {
// 2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
// NORTH -> WEST -> SOUTH -> EAST 순으로 회전
nextD = (nextD + 3) % 4;
nextR = robot.r + dr[nextD];
nextC = robot.c + dc[nextD];
// a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
if (map[nextR][nextC] == 0) {
robot.r = nextR;
robot.c = nextC;
robot.d = nextD;
cleanAble = true;
break;
}
// b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
}
// cleanAble이 false라면 네 방향 모두 청소가 이미 되어있거나 벽인 경우이므로
// 뒤쪽 방향의 벽 여부를 체크하여 후진 실시 or 종료가 이루어져야 함
if (!cleanAble) {
if (!checkBack(map)) {
return;
}
}
clean(map);
}
int main() {
// 첫째 줄 입력
scanf("%d %d", &N, &M);
// 둘째 줄 입력
scanf("%d %d %d", &robot.r, &robot.c, &robot.d);
// 셋째 줄 이후 입력
vector<vector<int>> map(N, vector<int>(M, 0));
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
scanf("%d", &map[i][j]);
}
}
clean(map);
printf("%d", answer);
return 0;
}스터디 (2022-02-06 SUN 📚)
✅ 스터디에서 얻은 Tip
👉 후진 방향 설정하는 부분을 나와 한 분을 제외하고는 모두
(robot.d+2) % 4 와 같이 깔꼼하게 한 줄로 계산해오셨다
한 번 아니고 두 번 회전하면 그것이 곧 후진 방향 인 것을..
한 번 회전하는 것은 (robot.d+3)%4 로 잘 계산해놓고
후진 방향은 다소 일차원적으로 계산해놓은 나는.. 멍청이....
// 후진 방향 설정 내 코드
int backD;
if (robot.d == NORTH || robot.d == SOUTH) {
backD = 2-robot.d; // 0:NORTH <-> 2:SOUTH
}
else { // robot.d == EAST || robot.d == WEST
backD = 4-robot.d; // 1:EAST <-> 3:WEST
}👉 갑자기 선배님이 재귀를 쓴 이유가 있나요? 라고 질문하셔서 당황..
질문은 항상 쉬운 것이든 어려운 것이든 머리를 하얗게 만든다 헝헝.. 😥
아직 그만큼 자신이 없어서겠지
사실상 입력 값이 3<=N,M<=50 으로 상당히 작아서
내맘대로 구현하면 되겠다~! 하고 짠 코드라서
의식의 흐름.. 이었습니다.. 라고 대답했는데 머쓱 💧
선배님도 사실상 이 문제는 입력 값이 작아서 상관 없지만
재귀는 최대 깊이가 커지면 문제가 될 수도 있기 때문에 꼭 염두에 두라고 말씀해주셨다
참고로 이 문제를 재귀로 풀면
최대 깊이는 모든 칸을 청소한다고 가정할 경우
지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽 이라는 조건 때문에
물론 정확히 N*M은 아니겠지만.. N*M 정도 라고 생각하면 될듯싶다
