kinssang   4년 전

  1. 현재 위치를 청소한다.
  2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
  3. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
  4. 왼쪽 방향에 청소할 방향이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
  5. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
  6. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
라고 되있는데, 5번, 6번 사항이 좀 이상한 듯 합니다.
네 방향이라고 하면 전 후 좌 우를 뜻할텐데, 전 후 좌 우가 모두 청소가 되어 있거나 벽이라면 아예 후진 자체가 안되지 않나요?
네 방향 모두 청소가 이미 되어있거나 벽인 경우엔 그냥 작동을 멈추지 후진은 안 될 것 같습니다.
애초에 5번 사항을 명시한 이유를 모르겠습니다. 6번 사항 밖에 존재하지 않는데.
저 사항이 둘 다 의미가 있으려면 네 방향이 아니라 세 방향으로 해야 맞을 듯 합니다. 현재 방향을 제외한 세 방향이요.

그리고 4번 사항도 문제인게 실제로 전 후 좌 우가 다 막힌 상황이라면 4->2->4->2->4->2 반복할 것 같은데요.  
문제 푸신 분들 계시던데 어떻게 푸신건지...

chogahui05   4년 전

전, 후, 좌, 우가 모두 청소가 되어 있는 경우와, 뒤에 벽이 있는 경우는 다를 수 밖에 없습니다. 

문제에 정확하게 명시가 되어 있습니다. 문제대로 구현하시기만 하면 풀리는 문제입니다.

어디가 이해가 안 가시는 것일까요?


예를 들어서

데이터가 아래와 같이 되어 있다고 해 봅시다.

그리고 출발 위치는 s로 표시를 해 놓았습니다. 출발 위치에서 저는 동쪽을 보고 있습니다.

그 경우 일단, 내 왼쪽에 길이 있기 때문에 쭉 위로 올라가겠죠?


그리고 나서, 5번 조건에 의해서 밑으로 내려옵니다. 그러면 청소기는 북쪽을 바라보고 있을 수 밖에 없겠죠?

북쪽의 왼쪽 방향은 서쪽입니다. 서쪽에 청소 안 한 공간이 있지요? 그러니까 방향을 꺽어서 청소를 하는 겁니다.

kinssang   4년 전

아 감사합니다. 무심코 벽 = 이미 청소한 영역이라고 생각해버렸네요.

chogahui05   4년 전

그런데. 프로세스 설명이 약간.. 이상한 건 맞는 듯 싶네요. 특히 2번하고 4번.

4번의 왼쪽 방향에 청소할 방향이 없다면 그 방향으로 회전하고 2번으로 돌아간다.


에서 밑줄친 부분 때문에 문제 푸시는 분들 해석에 따라서 2번 -> 4번 -> 2번 -> 4번 -> ...

이런 식으로도 해석이 가능할 듯 싶네요. 이 부분은 누군가 조금 다듬어야 할 듯 싶네요.

kinssang   4년 전

전 대강 반시계방향으로 빙글빙글돌면서 청소안한곳 찾는다!

정도로 해석했습니다. 아마 다들 비슷하게 해석하시지 않으셨을까요?

chogahui05   4년 전

저도 그렇게 해석했습니다. 만.. 자세히 읽어보니 다르게 해석될 여지도 조금은 있어보이더라고요.
실제로 다르게 해석하신 분들도 있는 듯 싶더라고요.

kinssang   4년 전

대략 이런식으로 적어준다면 깔끔하려나요?

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
3. 탐색 중인 방향에 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
4. 탐색하는 네 방향이 모두 청소가 이미 되어 있거나 벽인 경우에는
4 - 1 . 현재 방향 기준으로 뒤쪽 방향이 벽이 아니라면, 현재 방향을 유지한 상태로, 한 칸 후진을 하고 2번으로 돌아간다.
4 - 2 . 현재 방향 기준으로 뒤쪽 방향이 벽이라 후진이 불가능한 경우에는 작동을 멈춘다.

저는 4 - 1 기준으로 1번으로 돌아갔는데도 맞았습니다가 떴네요. 순서 차이라 그런가 봅니다.

zipbob   4년 전

제가 문제를 제대로 이해 못한 것 같은데

그냥 청소기 위치에서 위 아래 왼쪽 오른쪽 dfs로 0갯수 카운팅 하는 것과 뭐가 다른건가요??

kinssang   4년 전

'탐색'이라는 행동의 의미는 '한 칸'만 체크한다고 보시면 됩니다.


zipbob   4년 전

0인 곳이 잇으면 탐색하여 이동하고 

또 해당위치에서 0인 곳을 찾아 이동하고 갈 곳이 없을경우 후진하여 다시 탐색한다


 이 과정이 dfs와 유사한것 같은데 ...

kinssang   4년 전

듣고보니 그렇네요

zipbob   4년 전

나중에 집가서 풀어봐야겠네요..

감사합니다!

댓글을 작성하려면 로그인해야 합니다.