[code-up] 성실한 개미

영일이는 생명과학에 관심이 생겨 왕개미를 연구하고 있었다.

왕개미를 유심히 살펴보던 중 특별히 성실해 보이는 개미가 있었는데,
그 개미는 개미굴에서 나와 먹이까지 가장 빠른 길로 이동하는 것이었다.

개미는 오른쪽으로 움직이다가 벽을 만나면 아래쪽으로 움직여 가장 빠른 길로 움직였다.
(오른쪽에 길이 나타나면 다시 오른쪽으로 움직인다.)

이에 호기심이 생긴 영일이는 그 개미를 미로 상자에 넣고 살펴보기 시작하였다.

미로 상자에 넣은 개미는 먹이를 찾았거나, 더 이상 움직일 수 없을 때까지
오른쪽 또는 아래쪽으로만 움직였다.

미로 상자의 구조가 0(갈 수 있는 곳), 1(벽 또는 장애물)로 주어지고,
먹이가 2로 주어질 때, 성실한 개미의 이동 경로를 예상해보자.

단, 맨 아래의 가장 오른쪽에 도착한 경우, 더 이상 움직일 수 없는 경우, 먹이를 찾은 경우에는
더이상 이동하지 않고 그 곳에 머무른다고 가정한다.


미로 상자의 테두리는 모두 벽으로 되어 있으며,
개미집은 반드시 (2, 2)에 존재하기 때문에 개미는 (2, 2)에서 출발한다.

 

처음에 이 문제를 bfs로 해결하려 했지만,

결과를 보고 bfs 나 dfs로 푸는게 아니라고 생각했습니다.

왜냐하면 결과가 0인 부분은 전부 9로 도배가 되었기 때문입니다.

즉, 의미가 없다는 뜻이죠.

그래서 방법을 바꿨습니다.

어떻게 하면 이 문제를 풀수 있을까?

문제를 읽어보니 오른쪽과 아래로 갈수 있다고 합니다.

근데 오른쪽이 defualt고 오른쪽이 1일경우 아래로 내려간다고 했습니다.

즉. 오른쪽 여부를 확인하고 아래로 이동하는 이야기가 되었습니다.

그래서

#include <bits/stdc++.h>
using namespace std;
int arr[10][10];

void busy(int x, int y) {
  if (arr[x][y] == 2) {
    arr[x][y] = 9;
    return;
  }
  if (arr[x][y] == 0) {
    arr[x][y] = 9;
  }

  if (arr[x][y] == 1) {
    return;
  } 
  
  if (arr[x][y+1] == 1) {
    busy(x+1,y); // 아래
  }else 
   busy(x,y+1); // 오른쪽...
  

}
int main(void) {    
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);

  for(int i = 0;i<10;i++) {
    for(int j = 0;j<10;j++) {
      cin >> arr[i][j];
    }
  }

  busy(1,1);

  for(int i = 0;i<10;i++) {
    for(int j = 0;j<10;j++) {
      cout << arr[i][j] << " ";
    }
    cout << "\n";
  }
}

이런식으로 재귀를 이용하여 문제를 해결하였습니다.

아래로 갔을때는 오른쪽 여부가 1인지 확인한뒤 아래로 이동하고..

오른쪽은 별다른 조건이 없었기 때문에 그냥 했습니다.

하지만 이렇게 하면 안되는 이유는

바로 맨 아래 가 1일경우는 고려하지 않았습니다.

그래서 

if (arr[x][y] == 1) return;)경우에는 바로 빠져나가게 했습니다.

그러면 1일경우에는 무조건 종료가 되지만

그렇지 않는 경우에는 재귀상에 남아있기 때문에

동작하는것 같습니다.

 

마지막으로 먹이가 2이기때문에

이때는 모든 조건이 종료가 됩니다.