[백준 / #14503 / C++] 로봇청소기

이번 문제 또한 전에 필자가 다뤘던 문제들과 같은 문제이다.

 

https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

 

바로 문제 해석으로 들어가보자.

 

 

문제 해석:

 

 

이 문제의 로봇청소기가 움직이는 조건을 살펴보자.

 

 

로봇청소기는 우선 현재 있는 곳을 청소하고, 그 다음에 2번 탐색을 실행한다. 문제는 크게 생각할 것 없이 이러한 조건을 

 

따라가기만 하면 풀린다. 로봇청소기는 움직일 수 있는 경우의 수가 오직 1가지 이므로 너비우선탐색(BFS)와 같은 탐색을

 

굳이 할 필요가 없고 재귀의 형태로 깊이우선탐색(DFS)을 실행하면 된다. DFS라고 표현은 하였지만 결국에는 한 번의 탐

 

색을 끝마치면 문제의 답을 도출해내고, 문제에서 제시한 알고리즘을 그대로 따라가기만 하면 되기 때문에 시뮬레이션이

 

라고 볼 수 있다. 이 문제는 문제에 정답이 모두 나와있기 때문에 구현의 문제라고도 볼 수 있다. 따라서 자세한 내용은 코

 

드를 보면서 설명하겠다.

 

 

알고리즘 해설 및 코드:

 

 

 

 코드를 보면 ahead 함수는 내가 지금 바라보고 있는 방향으로부터 왼쪽의 방향을 구해주는 함수이다. 만약 동쪽에서 왼쪽

 

바라보게되면 d = 1 에서 d = 0이 되고, 이는 곧 왼쪽으로 돌 때마다 d -= 1과 같다. 하지만 d = 0에서 왼쪽으로 돌 때 d - 1

 

연산을 실행하면 d = -1 이 되므로 이에 대한 예외 연산을 포함한 함수가 ahead이다.

 

 

그리고 위에 mr과 mc 배열은 로봇청소기가 바라보는 방향으로 이동할 때의 배열에서의 움직임을 기록해둔 배열이다. d를

 

인덱스 값으로 사용하면 손쉽게 사용할 수 있기 때문에 다음에 이동할 위치를 계산해주기 편하게 배열로 기록해두었다.

 

 

문제에서 로봇청소기가 이동할 수 있는 경우는 후진하는 경우도 있다. 서남북의 경우에는 후진할 경우 d값에서 d - 2 >= 0

 

인 경우 그대로 반환해주고 d - 2 < 0인 경우 d + 2 를 반환해주면 후진하는 방향을 알 수 있다. 이러한 연산을 backward 함

 

수에서 실행한다.

 

 

그 후 dfs 함수에서 문제에서 제시된 조건을 그대로 실행하면 된다. 만약 왼쪽이 청소 가능할 경우 ahead함수를 통해 계산

 

한 방향으로 바라보도록 d를 바꿔주고, mr과 mc의 값을 각각의 r과 c에 더해줌으로서 위치를 바꿔준다. 그리고 cnt를 하나

 

증가시켜주면서 재귀를 호출해준다. 또한 turn을 인수로 받으면서 만약 하나씩 회전할 경우 turn 값을 하나씩 증가시켜주고

 

만약 turn값이 4로 한바퀴를 다 돌면 문제에서 제시한 조건인 뒤가 막혀있지 않다면 backward함수를 이용한 후진을, 뒤가

 

막혀있다면 로봇청소기의 작동을 중지하고 cnt를 저장하도록 연산한다. 여기서 turn값이 4이면 왼쪽의 연산이 불가능하여

 

머리의 방향이 4번 돌아서 원점으로 돌아왔다는 의미이므로 이렇게 재귀를 호출해주면 된다.

 

 

 

 

이번 문제는 문제에서 제시된 알고리즘만 그대로 따라가고 재귀를 사용한다면 쉽다고 생각이 드는 문제였다. 전에 다루었

 

던 문제들만 풀어봐도 이 문제는 쉽게 풀 수 있을 거라고 생각된다. 까다로운 조건도 없어서 괜찮게 풀 수 있었다. 

 

 

 

PS 드디어 백준 실버 달았다 ㅎ