공부흔적

문제 링크

풀이 )

  좌측 상단의 좌표를 (0, 0)이라 하고, 파이프의 방향을 가로는 0, 대각선은 1, 세로는 2라 하면,

  시작 좌표는 (1, 0)이고 방향은 0이라고 할 수 있다.

  매번 함수가 호출될 때 현재 방향에 따라 다음에 둘 수 있는 방향은 다음과 같다.

• 가로 -> 가로 | 대각
• 대각 -> 가로 | 대각 | 세로
• 세로 -> 대각 | 세로 

  따라서 각 상황에 맞게 좌표를 수정해주고, 다음 호출 시

• 좌표가 범위를 벗어나는 경우(x >= n || y >= n)
• 벽으로 가로 막혀있는 경우(home[y][x] == 1)
• 대각선으로 이동할 때(dir == 1) 위나 왼쪽이 벽으로 막혀있는 경우( (y>0 && home[y-1][x]) || (x>0 && home[y][x-1]) )

  위의 3가지의 경우 함수를 종료 시켜주고,

  마지막인 x, y좌표가 각각 n-1인 경우 가짓수를 하나 늘려준다.

#include <cstdio>

int dx[3] = {1, 1, 0};
int dy[3] = {0, 1, 1};
int n, ans, home[17][17] = {0, };

void dfs(int x, int y, int dir);

int main(void)
{
  scanf("%d", &n);
  for(int i = 0; i < n; ++i)
    for(int j = 0; j < n; ++j)
      scanf("%d", home[i]+j);

  dfs(1, 0, 0);
  printf("%d\n", ans);
}

void dfs(int x, int y, int dir)
{
  if(x >= n || y >= n)
    return;
  if(home[y][x])
    return;
  if(dir == 1){
    if((y>0 && home[y-1][x]) || (x>0 && home[y][x-1]))
      return;
  }
  if(x == n-1 && y == n-1){
    ++ans;
    return;
  }

  if(dir == 0){
    dfs(x+dx[0], y+dy[0], 0);
    dfs(x+dx[1], y+dy[1], 1);
  }
  else if(dir == 1){
    dfs(x+dx[0], y+dy[0], 0);
    dfs(x+dx[1], y+dy[1], 1);
    dfs(x+dx[2], y+dy[2], 2);
  }
  else{
    dfs(x+dx[1], y+dy[1], 1);
    dfs(x+dx[2], y+dy[2], 2);
  }
}

주의점 )

  함수를 종료시키는 경우를 답을 증가시키는 경우보다 위에 두어야 답이 아닌데 세는지 않을 수 있다.

  ex ) dfs( )의 4번째 if 블록을 3번째 if 블록과 위치를 바꾸게 된다면

  4

  0 0 0 0

  0 0 0 0

  0 0 0 1

  0 0 1 0

  과 같은 입력에 대해서 오답을 출력하게 된다.