https://www.acmicpc.net/problem/14503
난이도: solved.ac 골드 5
문제는 정말 길지만 시키는 대로만 만들면 돼서 생각보다 쉬운 문제다
그치만,, 구현하는데 실수를 해서 애를 먹었는데 아무도 궁금해하진 않겠지만 내가 실수했던 부분을 기록해 보겠다
(똑같은 실수를 하는 분들을 위해...)
분명 오류 난 부분도 없는데 문제의 예제 2를 입력하면 출력으로 20이 나왔다 ㅠ
알고 보니 문제에서 설명하는 로봇 청소기 작동 단계 2번 부분에서
'바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.'를 구현할 때
'바라보는 방향을 유지한 채로'는 맞게 구현했지만 '한 칸 후진'이 아닌 '앞으로 한 칸'으로 구현했다
이것 때문에 내가 문제를 잘못 이해한 줄 알고 문제를 여러 번 다시 읽었던 걸 생각하면...ㅎ
문제의 지문이 조금 헷갈리는 경향이 있기도 한데 그런 분들을 위해
예제 입력 2를 토대로 청소기가 이동하는 좌표를 나타내보겠다
(7, 4) 1
(7, 3) 2
(8, 3) 3
(8, 4) 4
(9, 4) 5
(9, 5) 6
(8, 5) 7
(7, 5) 8
(6, 5) 9
(6, 4) 10
(5, 4) 11
(5, 3) 12
(6, 3) 13
(6, 2) 14
(7, 2) 15
(7, 1) 16
(8, 1) 17
(8, 2) 18
(9, 2) 19
(9, 3) 20
(9, 1) 21
(9, 6) 22
(9, 7) 23
(9, 8) 24
(8, 8) 25
(7, 8) 26
(6, 8) 27
(5, 8) 28
(5, 7) 29
(4, 7) 30
(4, 6) 31
(5, 6) 32
(5, 5) 33
(4, 5) 34
(4, 4) 35
(3, 5) 36
(3, 6) 37
(3, 7) 38
(3, 8) 39
(2, 8) 40
(1, 8) 41
(1, 7) 42
(1, 6) 43
(1, 5) 44
(1, 4) 45
(1, 3) 46
(2, 3) 47
(2, 2) 48
(3, 2) 49
(3, 1) 50
(4, 1) 51
(5, 1) 52
(5, 2) 53
(6, 1) 54
(2, 1) 55
(1, 1) 56
(1, 2) 57
그림으로 나타내면 아래와 같다
빨간 박스는 출발점인 (7, 4)이고, 노랑 → 초록 → 파랑 → 분홍색 순서로 보면 된다
나름 주석을 열심히 달면서 내 코드가 쉽게 이해되도록 해봤는데 도움이 되었으면 좋겠다...
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define UNCLEANED 0
#define WALL 1
#define CLEANED 2
int clean(int** room, int y, int x, int* dir, int* cnt);
int find_dir(int** room, int y, int x, int* dir);
int main() {
int N, M;
int i, j;
scanf("%d %d", &N, &M);
/* 2차원 배열 동적 할당 */
int** room = (int**)malloc(sizeof(int*) * N);
for (i = 0; i < N; i++)
room[i] = (int*)malloc(sizeof(int) * M);
/* y, x: 청소기의 좌표 (y행 x열), dir: 방향, cnt: 청소한 칸의 개수 */
int y, x, dir, cnt = 0;
scanf("%d %d %d", &y, &x, &dir);
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++)
scanf("%d", &room[i][j]);
}
clean(room, y, x, &dir, &cnt);
printf("%d", cnt);
/* 동적 할당 해제 */
for (i = 0; i < N; i++)
free(room[i]);
free(room);
return 0;
}
int clean(int** room, int y, int x, int* dir, int* cnt) {
if (room[y][x] == UNCLEANED) { // 청소가 안 되어 있을 때
room[y][x] = CLEANED;
(*cnt)++;
}
/* 동서남북 모두 0이 아닐 때 */
if (room[y - 1][x] && room[y][x + 1] && room[y + 1][x] && room[y][x - 1]) {
if (room[y + 1][x] == CLEANED && *dir == 0) // 북쪽을 바라보며 뒤로 갈 수 있을 때
clean(room, y + 1, x, dir, cnt);
else if (room[y][x - 1] == CLEANED && *dir == 1) // 동쪽을 바라보며 뒤로 갈 수 있을 때
clean(room, y, x - 1, dir, cnt);
else if (room[y - 1][x] == CLEANED && *dir == 2) // 남쪽을 바라보며 뒤로 갈 수 있을 때
clean(room, y - 1, x, dir, cnt);
else if (room[y][x + 1] == CLEANED && *dir == 3) // 서쪽을 바라보며 뒤로 갈 수 있을 때
clean(room, y, x + 1, dir, cnt);
else
return 0;
}
/* 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우 */
else {
find_dir(room, y, x, dir); // 반시계 방향으로 90도 회전하면서 청소할 방향을 찾음
if(*dir == 0)
clean(room, y - 1, x, dir, cnt); // 북
else if(*dir == 1)
clean(room, y, x + 1, dir, cnt); // 동
else if(*dir == 2)
clean(room, y + 1, x, dir, cnt); // 남
else if(*dir == 3)
clean(room, y, x - 1, dir, cnt); // 서
}
}
/* 반시계 방향으로 회전하면서 청소할 방향을 찾는 함수 */
int find_dir(int** room, int y, int x, int* dir) {
*dir = *dir - 1; // 반시계 방향으로 90도 회전
if (*dir == -1)
*dir = 3;
if (*dir == 0) {
if (room[y - 1][x] == UNCLEANED) // 북쪽이 청소되지 않은 경우
return 0; // 갈 수 있는 방향 찾기 성공
else
find_dir(room, y, x, dir);
}
else if (*dir == 1) {
if (room[y][x + 1] == UNCLEANED) // 동쪽이 청소되지 않은 경우
return 0; // 갈 수 있는 방향 찾기 성공
else
find_dir(room, y, x, dir);
}
else if (*dir == 2) {
if (room[y + 1][x] == UNCLEANED) // 남쪽이 청소되지 않은 경우
return 0; // 갈 수 있는 방향 찾기 성공
else
find_dir(room, y, x, dir);
}
else if (*dir == 3) {
if (room[y][x - 1] == UNCLEANED) // 서쪽이 청소되지 않은 경우
return 0; // 갈 수 있는 방향 찾기 성공
else
find_dir(room, y, x, dir);
}
return 0;
}