문제 유형
7*7 크기의 미로가 주어지고, 도착 지점인 (7,7) 좌표에 도착하는
모든 경우의 수를 구하라
필요자료구조
int dx[] // (x좌표 기준 동서남북 초기화),
int dy[] // (y좌표 기준 동서남북 초기화),
int nx[] // (내가 이동할 x 좌표),
int ny[] // (내가 이동할 y 좌표),
int arr[][] // (미로 초기화),
DFS() 메서드 // 핵심 로직,
answer // 출력
핵심 문제 해석
첫째 모든 경우의 수를 구할 때는 DFS를 사용하자
둘째 경로가 동서남북으로 뻗어갈 수 있다.
문제 풀이 과정
2차원 배열의 1번 인덱스를 x, 2번 인덱스를 y 좌표로 설정하고
동서남북으로 움직이기 때문에 dx 배열과 dy 배열을 선언해줬다.
한번 지나간 경로는 다시 지나가선 안되므로 내가 지나간 좌표는
값 1로 처리해줬다.
1은 벽이고, 0은 길이므로 값이 0일 때만 이동할 수 있다.
내가 이동할 좌표가 0보다 커야하고, 7보다는 작거나 같아야 한다는
조건을 걸어준 다음
DFS를 재귀 호출하도록 선언하고
스택에서 제거될 때 다른 경로의 수도 찾아야하므로 백트래킹되도록 선언해줬다.
최종적으로 내가 이동한 경로가 7,7 좌표에 서있을 때 answer++ 해줌으로써 경로의 수를 추가해줬다.
arr[1][1] = 1로 초기화 시켜줘야 한다.
그 이유는 아래와 같다.
첫 시작점이 1,1 좌표일 때 뻗어나갈 수 있는 방향은 두 방향이다.
우와 하 방향, 상과 좌 방향은 좌표가 0이 되므로 이동할 수 없기 때문이다.
그런데, 만약 두가지 방향으로 경로의 수를 탐색한다면
한가지 방향으로 출발했을 경우 x2배가 되어버린다.
그러므로 한가지 방향으로만 출발할 수 있도록
arr[1][1] = 1로 설정해줘야 한다.
핵심 코드
public void DFS(int rL, int cL) { // rL = rowLevel, cL = column Level
if (rL == 7 && cL == 7) answer++;
else {
for (int k = 0; k < 4; k++) {
int nx = rL + dx[k];
int ny = cL + dy[k];
if (nx > 0 && ny > 0 && nx <= 7 && ny <= 7 && arr[nx][ny] == 0) {
arr[nx][ny] = 1;
DFS(nx, ny);
arr[nx][ny] = 0;
}
}
}
}개선된 점
첫째 문제 이해 능력이 향상되었다.
둘째 자료구조, 알고리즘을 그려가거나, 상상해보면서
문제를 풀이한다.
셋째 웬만하면 답을 보지 않는다.
문제를 풀다보면 이 문제는 시간을 들이면 풀 수 있을지
시간을 오래 잡아도 풀 수 없는 문제인지 감이 온다.
감각에 따라서 답을 보는 편인데,
이번 문제는 2일 동안 고민하다가 결국 강의를 시청했다.
피드백, 개선할 점
첫째 논리적으로 문제를 해결해 나갈 때 가장 중요한 것은 방향이다.
잘못된 방향으로 시작하면 대부분 정답에 도달할 수 없는게
알고리즘이기 때문이다.
그래서 한걸음 한걸음 논리적인 근거하에 로직을 작성해야 한다.
나는 어느정도 논리 + 감으로 코드를 작성하다 보니 이중 for문을 만들어서 DFS 로직을 작성했는데
그렇게 되면 무한루프문에 빠지게 돼버린다.
앞으로는 논리적인 근거의 비중을 최대한으로 두고 로직을 작성해나가야 할 것 같다.
느낀점
첫째 논리적 사고는 결국 상상력인 것 같다.
문제를 풀다보면 이 로직을 작성했을 때 데이터가 어떤 식으로 흘러가게될지를 상상해야 한다.
그 결과가 옳게된 방향이라면 그 로직을 사용하고,
잘못된 방향이라면 로직을 수정해야 한다.
상상력은 집중력, 논리력과 비례하는 것 같다.
상상을 많이 하자!
둘째 오늘 안풀리던 문제가 내일 금방 풀리는 경우가 꽤 있다.
오늘 머리를 아무리 쥐어짜도 답이 안보이던 문제가
내일 문제를 접근하면 신기하게도 정답으로 향하는 길이 뻥 뚫린 것처럼 쉽게 풀릴 때가 있다.
뭔가에 홀린 것처럼 로직을 다 작성하고 실행시키면
정답이다.
나는 문제가 안풀릴 때마다 아래 대사를 상기한다.
"수학적 용기는 오늘 못 푼 문제를 내일 푸는 끈기"
-이상한 나라의 수학자 최민식 대사 中-
