#. Problem * The copyright in this matter is in Inflearn #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract - 7 * 7 격자판 미로 탈출 경로의 가지수 - 출발점은 (1,1), 도착점은 (7,7) - 격자판 1은 벽, 0 은 통로 - 상하좌우로만 이동 3. Create solution plan (select Algorithm, Data structure) - DFS 4. Prove the plan (check performance time and usage memory) 5. Carry out the plan 6. Look back on the plan and find a way to improve it #. Solve 격자는 상,하,좌,우 로 이동할 수 있다고 했다. 출발지점부터 편하게 상, 하, 좌, 우 이렇게 접근해보자 먼저 과정을 스택에 쌓으면서 그려보자. (1,1) 부터 출발해보자. D(x, y-1) // 상 D(x, y+1) // 하 D(x-1, y) // 좌 D(x+1, y) // 우 하단으로 먼저 갈 것이므로 D(x, y+1) 로 호출해보자. ... 하단으로 더이상 갈 수 없다면, return을 해주어야 할 것이다. if(map[x][y] == 1) return; if(x > n || y > n ) return; else { D(x, y-1) // 상 D(x, y+1) // 하 D(x-1, y) // 좌 D(x+1, y) // 우 } 지금 상태에서 상, 하, 좌 가 모두 안 되므로, 우측으로 이동한다.
여기서 의문이, 이미 왔던 길을 어떻게 판별할지인데, 이미 왔던 길은 1로 체크하는 것이 좋을 듯 하다. if(map[x][y] == 1) return; if(x > n || y > n ) return; else { map[x][y] = 1; D(x, y-1); // 상 D(x, y+1); // 하 D(x-1, y); // 좌 D(x+1, y); // 우 map[x][y] = 0; } 이렇게되면 다음으로 좌측은 이미 지나간 길이라 1일테고, 하단으로 가겠군
... 이 과정으로 코딩해보면 될것 같다. if(map[x][y] == 1) return; if(x > n || y > n || x < 1 || y < 1) return; else if(x == n && y == n) cnt++; else { map[x][y] = 1; D(x, y-1); // 상 D(x, y+1); // 하 D(x-1, y); // 좌 D(x+1, y); // 우 map[x][y] = 0; } #. Code
와아아.. 이번에는 스택으로 그리면서 코드를 만들어나가니깐 한 번에 성공했다..! 비록 쉬운 문제일지라도 나에겐 헷갈리고 복잡했던 재귀함수를 이제 어느정도 이해할 수 있을 것 같다. 이런 기분으로 PS를 하는구나.. 캬캬캬 앞으로는 DFS 문제는 스택을 그려보면서 함수를 만들어나가도록 해야겠다! line 11) 벽으로 가려고 할 경우 return line 14) 격자의 범위를 벗어날 경우 return line 16) 도착지점에 도달할 경우 cnt++ line 20~27) line 20, 지나온 길을 1로 치환하여 탐색 방향이 겹치지 않도록 함 line 22~25, 상, 하, 좌, 우 로 이동하는 재귀 함수 호출 line 27, 앞 길을 다 탐색했다면 다시 0으로 치환하여 다른 경우의 수에 반영이 되지 않도록 함 #. Other code
강사님은 이동경로를 저장하는 배열을 따로 사용하셨고, dx, dy 배열(앞으로 갈 방향)을 사용하셔서 더 코드를 간결하게 짜셨다. 그리고 내 코드는 함수에 들어왔을 때, 격자를 벗어난 유무와 길의 상태를 확인했는데, 위 코드는 함수에 넣기 전에 확인하여 재귀함수의 깊이를 줄일 수 있던 것 같다. line 10~25) DFS 함수에서 도착지점에 도달했을 경우와, 그렇지 않을 경우, 두 경우로 나누었고 line 11) 마찬가지로 (7, 7) 에 도착했을 때 cnt++ 를 해주었다. line 14 부터는 for문을 돌면서 앞으로 갈 방향을 정하여 재귀함수를 호출하는데 , line 15~16 에서 앞으로 갈 격자의 좌표를 먼저 저장하고 line 17) 앞으로 갈 좌표가 격자를 벗어날 경우 continue line 19) 앞으로 갈 좌표가 길에 맞고, 왔던 길이 아닐 경우 line 20~22) ch 배열에 체크하고 해당 좌표를 담아서 재귀함수를 호출한다. 재귀함수가 끝나면 ch 배열에 체크를 해제하고 다음 방향을 탐색한다. 전체적인 로직을 강사님과 유사하게 잘 구현한 것 같다. Yeahhhhhhhhhh~~! #. Result - Input -------------------------------------------------------- 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 0 0 0 0 ------------------------------------------------------------------ - Output -------------------------------------------------------- 8 ------------------------------------------------------------------ |