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

구현 / 시뮬레이션 문제.

구현하는 문제는 뭔가 테스트 케이스가 많이 필요한 것 같다.

아래 올린 링크에서 테스트 케이스를 보고 나서야 풀 수 있었다.

글 읽기 - [로봇 청소기] 테스트 케이스(반례) 공유합니다.

 

구현 문제는 뭔가 이해하기도 어렵고, 이해했다쳐도 이걸 코드로 어떻게 짜야할지 잘 생각이 안난다.

무한루프와 틀렸습니다를 거치고 반례를 통해 문제점을 찾은 후에야 맞출 수 있었다.

 

처음 이 문제를 봤을 때

처음에는 그냥 현재 보는 방향에 따라 모든 조건을 다 걸어주려고 했다.

그런데 이렇게 짜면 예외처리할 상황이 너무 많기도 하고, 코드도 너무 비효율적으로 길어지는 것 같아서

다른 방법을 생각해봤다.

방향이 0, 1, 2, 3으로 주어져 있어서 배열로 구현하고 싶었고, 방향에 따른 왼쪽에 대한 정보가 어떻게 될 지 생각해보기로 했다. 각 방향에 따라 왼쪽 방향이 무엇인지, 또 왼쪽 방향의 좌표가 무엇인지 어떻게 알 수 있을까?

• 북쪽(0)일 경우 왼쪽방향은 서쪽(3)이고 왼쪽 index는 x가 -1, 후진은 y가 +1
• 동쪽(1)일 경우 왼쪽방향은 북쪽(0)이고 왼쪽 index는 y가 -1, 후진은 x가 -1
• 남쪽(2)일 경우 왼쪽방향은 동쪽(1)이고 왼쪽 index는 x가 +1, 후진은 y가 -1
• 서쪽(3)일 경우 왼쪽방향은 남쪽(2)이고 왼쪽 index는 y가 +1, 후진은 x가 +1

라는 정보를 얻을 수 있었다. 따라서 이를 pair<int, pair<int, int>> 자료형에 저장하고,

왼쪽 좌표와 왼쪽 방향을 현재 방향에서 얻도록 만들었다.

 

여기까지는 잘 구현했는데 재귀함수로 갈 수 있는 곳을 찾도록 만드니까 무한루프에 빠지는(혹은 시간이 너무 오래걸리는) 현상이 발생했다. 그래서 재귀함수를 쓰돼, 현재 왼쪽이 0이 아닌 경우에는 왼쪽 방향과 왼쪽 좌표를 이용해서 계속해서 찾도록 만들었다.

 

문제풀이

 

사용한 STL과 변수

STL은 따로 사용한 것은 없다.

• height, width : 높이와 너비 변수이다.
• room 배열 : 현재 방의 정보를 입력받는 배열이다.
• robotY, robotX, robotDirection : 최초의 로봇의 정보를 담는 변수들이다.
• result : 청소하는 방의 개수를 담는 변수이다.
• directionGoSystem 배열 : pair 자료형으로, 위에서 설명했듯이 왼쪽 방향과 왼쪽의 좌표를 얻을려면 현재 좌표에서 어떻게 더해줘야 하는지를 담는 배열이다.
• directionBackSystem 배열 : pair 자료형으로, 현재 방향에서 후진을 하려고 할 때, 현재 좌표에서 어떻게 더해줘야 하는지를 담는 배열이다.

 

청소 메서드 - 1

다음은 청소를 하는 메서드이다. DFS와 비슷한 느낌이라고 생각하면 된다.

메서드에 진입할 때 매개변수 y와 x를 이용해서 방의 정보를 받아온 후에, 만일 방이 0일 경우, 2로 청소해줬다고 표시를 해준다.(1로 해도 상관은 없다.) 그리고 결과값에 1을 더해준다.

 

그리고 위에서 입력해줬던 정보(pair배열)와 현재 로봇이 보는 방향을 나타내는 direction 매개변수로 왼쪽방향, 왼쪽의 좌표를 받아오고 후진을 대비해서 후진의 좌표를 입력받아준다.

 

청소 메서드 - 2

그 다음으로는 만일 현재 보는 방향에서 왼쪽 방의 정보가 0, 즉 청소가 되지 않은 상태라면 그냥 바로 왼쪽방을 진입해서 청소를 해주면 된다. 그리고 방향을 왼쪽방향으로 보게 매개변수로 방향의 정보를 넘겨준다.

 

만일 왼쪽 방이 청소가 필요가 없는 방이라면

1. 상하좌우가 모두 청소가 필요가 없는 방일 경우 -> 후진할 곳이 1(벽)이라면 청소기를 종료한다. / 후진할 곳이 1(벽)이 아니라면 후진한다.
2. 상하좌우 중 하나라도 청소가 필요한 경우 -> 반복문을 통해서 왼쪽부터 찾아준다. 지금 왼쪽의 방향에서의 왼쪽의 좌표를 받아온 후, 마지막으로 왼쪽방향도 왼쪽의 왼쪽으로 나타내도록 해준다. 이렇게 반복문을 돌려서 청소가 필요한 곳을 찾는다. 그 후, 찾은 좌표와 방향을 가지고 청소 메서드를 호출한다.

왼쪽의 왼쪽이라고 설명하니 조금 복잡하게 느껴진다.

예를 들어서 만일 메서드에 진입할때 북쪽을 보고있었고 3, 2의 좌표라고 생각하면

• 북쪽의 왼쪽은 서쪽이고 서쪽의 좌표는 3, 1이 된다. leftDirection은 서쪽을, leftY는 3을 leftX는 1을 나타내게 된다.
• 근데 만일 서쪽은 청소를 할 필요가 없는데 다른 한 곳이 청소가 필요한 곳이 있어서 찾게 된다면 서쪽의 왼쪽부터 찾으면 된다.(서쪽은 이미 청소할 필요가 없다는 것을 첫번째 if문에서 확인했으므로) 따라서 leftY, leftX 값을 서쪽의 왼쪽의 정보를 담는 배열을 이용해서 더해준 후, 서쪽의 방향을 남쪽으로 바꿔준다. 이를 0이 나올때까지 반복한다.

이런 식으로 하면 문제의 조건처럼 왼쪽부터 차례대로 방을 탐색할 수 있게된다.

 

메인함수

메인함수는 간단하다. 방의 높이와 너비를 입력받고, 로봇의 정보를 입력받는다.

그리고 방의 정보들을 입력받은 후, 로봇의 정보를 가지고 청소 메서드를 실행시킨다.

그리고 결과값을 출력하면 끝이다.

 

구현 문제는 언제나 빡센것 같다.

연습을 좀 더 많이 해볼 필요가 있을 것 같다.

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인이 가능하다.