graph, dfs 3

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

문제 사이트 주소입니다.

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

전형적인 dfs로 풀 수 있는 이전에도 비슷한 문제를 풀었던것 같은데 갈 수 있는 길이 주어질 때 가장 빠르게 갈 수 있는 거리를 구하는 문제입니다.

배열의 크기와 갈 수 있는길(0), 없는길 (1)을 받습니다.  입력받는 방법도 다양하게 알아둬야 나중에 알고리즘 테스트시 입력가지고 시간을 소비하지 않을 수 있습니다.  

여기서는 띄워쓰기 구분이 없는 숫자 형식으로 입력을 받는데 하나씩 받아야 하므로 %c로 받고 -'0'을 해줘서 숫자로 바꿔줍니다.  그리고 enter를 입력받지 않으면 안되는데 이것도 마지막에 입력받도록합니다.

dfs를 위한 재귀함수는 언제나 비슷합니다.  함수를 호출하고, 갈 수 있는 곳(상, 하, 좌, 우)를 판별한 후에 갈 수 있으면 해당길은 갔다는 표시를 하고 진행합니다.  dfs 특성상 끝까지 진행하고 함수를 나올 때는 나온 길에 갔다는 표시를 지웁니다.  그리고 다음 검사를 합니다(상의 길을 갔으면 다음은 하).  탈출 조건은 끝점에 도달했을 때로 하며 이 때 카운트가 최소인 경우를 구합니다.  갈 수 있는 길을 판별할 때 배열의 범위를 검사해주는 것도 해야합니다.