graph, dfs 2

문제는 더블릿 16 graph, dfs에 있는 snail_trails입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/snail_trails/snail_trails.php?pname=snail_trails

맵에서 갈 수 없는 곳이 있을 때 상하좌우로 중복되지 않고 끊기지 않기 최대한 많이 움직일 수 있는 거리를 찾는 것이 목적입니다.

문제 그대로 한번 방향을 잡고 막힐 때까지 가면서 카운터를 세고 가장 높은 카운터를 출력해주면 됩니다.

일단 문제의 맵을 입력받습니다.  그리고 시작점부터 우측 혹은 아래로 이동을 시작하는데 막다른 곳이 나오면 방향을 바꾸고 지나갔던 곳이 나오면 종료하는 재귀를 사용합니다.

종료 조건이 지나간 곳을 만났을 때 입니다.

다음 위치는 현재 방향의 한칸 앞이 되며 다음 위치가 범위를 벗어나거나 장애물의 위치이면 방향을 바꿉니다.  이 때 가던 방향과 수직으로, 2번 바꿀 수 있습니다.  예제로 보면 처음 오른쪽으로 가다가 첫 장애물을 만났을 때 위로도 갈 수 있고 아래로도 갈 수 있는데 위는 범위를 벗어나니 아래로 가게 됩니다.  왔던 방향의 반대방향으로는 갈 수 없습니다.  

이렇게 해주기 위해 현재 가던 방향을 저장할 변수가 필요합니다.  그리고 가던 방향이 좌우일 경우, 계속 좌우로 가면서 카운터를 늘려주고 장애물일 경우 위아래로 방향을 바꿔 움직이며 방문한 곳일 경우 종료합니다.  재귀 함수의 틀을 보면

sn(현재 x, 현재 y, 방향 d, 카운터 s){

종료 조건

방문 표시

카운터 증가

다음위치 xx=x+d

다음위치 yy=y+d

if(범위를 벗어나거나 장애물이면){

 if(방향을 바꿔서){

  if(위아래로 가던 경우){

   좌우로 이동 재귀 호출

  }

  else(좌우라 가던 경우){

   위아래로 이동 재귀 호출

   }

  }

 else(갈 수 있으면){

   그대로 진행 재귀 호출

  }

방문 표시 해제

}

과 같은 꼴이 됩니다.

이는 dfs 문제를 풀 때 보통 나오는 재귀의 틀이므로 기억해두면 좋습니다.  해당 위치를 탐색할 때 방문 표시를 하고 다시 돌아갈 경우 방문 표시를 해제합니다.

하나씩 따라가다 보면 저 알고리즘이 어떻게 맵 전체를 조건에 따라 돌아 볼 수 있는지 알 수 있습니다.