과제 5

[문제]

n x n 크기의 격자에서 (0, 0)부터 (n, n)까지 격자선을 따라 갈 수 있는 경로 중, 한 번 갔던 점은 다시 방문하지 못한다고 할 때 가능한 전체 경로의 수 구하기.

 

→ 격자 정보를 저장하는 클래스가 주어짐.

 

[해결]

  격자 상의 경로 문제라고 하면 보통 Left top에서 right bottom 방향으로만 움직이는 문제 풀이가 대부분이지만, 이 문제는 이동 방향에는 아무런 제약이 없다. 방문하지 않은 점이기만 하면 Top/Bottom/Left/Right 모든 방향으로 움직일 수 있기 때문에 이 문제가 경우의 수가 훨씬 더 무지막지하게 나옴.

  어차피 진행 방향에는 아무 제약이 없으므로, 신경써야 할 것은 '지나갈 점이 이미 지났던 점인가?' 밖에 없는데, 여기서 스택을 쓰네 마네 하며 고민하다가 좀 이상하게 풀었다.

 

→ 해당 점을 지나갔는지 지나가지 않았는지의 여부를 기록할 bool형의 이차원 배열을 생성. 배열의 크기는 (n+1) * (n+1)로 생성하면 됨.

* n x n 크기의 격자 속에는 (n+1) * (n+1) 개의 점이 들어있으므로.

→ 재귀를 사용하여 한 점의 4방향(위, 아래, 왼쪽, 오른쪽)을 모두 탐색해가며 진행, 점을 지날 때마다 위에서 만든 배열의 해당 좌표를 true로 바꿔줌. true인 점은 이미 방문한 점이므로 탐색 시 제외된다.

→ 함수의 호출이 끝날 때마다 현재 좌표에 해당하는 배열 값을 false로 바꿔줌. 그래야 그 다음 호출에서 탐색하는 것이 가능해진다.

→ 현재 좌표가 목적 좌표 (n, n) 일 경우 경로의 수를 1씩 증가시킴.

 

[코드]

* 격자 정보를 저장하는 클래스는 따로 첨부하지 않았다. 내가 짠 클래스가 아니므로...

#include "grid.h"
#include <iostream>

using namespace std;

unsigned long long grid::numOfWays(void){  
  sum = 0; //탐색을 진행하며 경로 수를 셀 때 사용
  result = 0;
  
  int size = (n+1) * (n+1); //(n * n)개의 격자 속 점의 개수

  //g : 격자 속 점의 방문 여부를 판별하기 위한 이차원 배열
  //클래스 속에 선언되어 있어 여기엔 자료형이 나오지 않지만 bool ** 형이다.
  g = new bool * [n+1]; 
  for (int i = 0; i < n + 1; i++)
    g[i] = new bool[n + 1];
  
  for (int i = 0; i < n + 1; i++)
    for (int j = 0; j < n + 1; j++)
      g[i][j] = false;

  search(0, 0);

  result = sum;

  delete g;

  return result;
}

void grid::search(int p, int q){ 
  if (p == n && q == n) {
    g[p][q] = true;

    sum ++;
  }
  else {
    g[p][q] = true;
    
    if ((p-1) >= 0 && !g[p-1][q]) {
      g[p-1][q] = true;
      search(p-1, q);
    }
    if ((p+1) < (n+1) && !g[p+1][q]) {
      g[p+1][q] = true;
      search(p+1, q);
    }
    if ((q-1) >= 0 && !g[p][q-1]) {
      g[p][q-1] = true;
      search(p, q-1);
    }
    if ((q+1) < (n+1) && !g[p][q+1]) {
      g[p][q+1] = true;
      search(p, q+1);
    }    
  }

  g[p][q] = false;
}

◇

 

  하도 어려울 거라고 겁을 주셔서 엄청 쫄았었는데 상당히 무식하게 풀었다. 이걸 방법이라고 할 수 있는지도 모르겠고 아무리 구글링해서 좀더 깔끔한 코드가 있는지 찾아보려 해도 좀처럼 보이지가 않아서 일단 마무리 짓고 넘어가기로 함. 과제 제출 서버에서는 n이 6일 때까지만 돌려보고, 그 이상은 못 돌려봤다(너무 오래 걸려서...). 이 문제 자체가 수가 올라갈 수록 경우의 수가 기하급수적으로 늘어나기 때문에 더 큰 수에 대해서 테스트 하지 못하는 건 어쩔 수 없지 않나 싶다. 풀이도 딱히 보장된 풀이가 아니라서 수가 계속해서 증가하면 다른 풀이보다 느릴지 어떨지도 확실하게 못 말하겠음.