우선 코드를 dfs로 구현하지 않으셨습니다. 함수 이름은 dfs로 하셨지만 구현은 그리디하게 하셨네요.
코드를 보면 for문에서 로봇이 빈 공간을 만나면 이동을 한 뒤 break를 함으로서 루프를 탈출하고 있습니다.
회전하다 처음으로 비어있는 공간에 무조건 이동한 뒤 다른 경우는 제외되는 것이죠.
exit(0)대신 return을 사용하면 답이 여러개가 나온다고 하셨는데 한개만 나올 것입니다.
flag변수를 없앨 경우에는 dfs처럼 변하게 됩니다.
flag변수를 없앤다는 것은 로봇이 이동을 했던 하지 않았던 뒤에 벽이 없다면 후진을 한다는 것입니다.
바로 여기서 분기가 생기게 됩니다. 따라서 최종적인 로봇의 경로가 여러 개가 될 수 있습니다.
하지만 올바른 로봇의 경로는 항상 첫 번째가 됩니다. 왜냐하면 그리디하게 움직이는 로봇이 옳은 경로로 움직이고 있기 때문입니다.
즉, 빈 공간으로 이동하는 명령이 후진하는 명령보다 코드상에서 앞서고 있기 때문에 첫 번째 dfs결과가 정답이 되는 것입니다.
shinbian11 2년 전
1번 질문)
현재의 위치에서 왼쪽 방향부터 총 4방향을 모두 탐색한 다음, 이 중에 청소 가능한 방향이 단 한곳도 없을 때 그제서야 44 ~ 57번째 줄의 내용(뒤쪽으로 후진 가능한지 따지는 부분)을 실행해야 하는 것이잖아요? 그래서 flag 라는 변수를 이용하여 flag 가 for문을 통과한 이후에도 false일때만 실행이 되도록 처리를 했는데요. (27, 29, 43번째 줄) => 혹시나 싶어서 이 flag 변수를 없애고 (27, 29, 43번째 줄 내용 삭제) 실행을 했는데도 잘 되는데, 그 이유가 궁금합니다.
2번 질문)
55, 56번째 줄에서 exit(0); 이 아닌 return; 을 쓰면 결과들이 여러 로개가 주르륵 나오는데요, 그 중에서 첫번째로 출력되는 값이 정답이기 때문에, exit(0);을 써야 되는 것은 이해 했는데요. 왜 dfs를 통해 탐색한 결과 중 첫번째로 출력되는 값이 곧 정답인가요?
dfs를 통해 탐색을 하다 마지막까지 살아남은 dfs가 가장 첫번째로 출력이 되고, 그것이 다시 말해, 가장 많이 청소한 결과값을 가지고 있는 결과라서 그런 것인가요?