문제 유형
7*7 크기의 미로가 주어지고, 도착 지점인 (7,7) 좌표에 도착하는
최단경로의 길이를 구하라
필요자료구조
int dx[] // (x좌표 기준 동서남북 초기화),
int dy[] // (y좌표 기준 동서남북 초기화),
int nx[] // (내가 이동할 x 좌표),
int ny[] // (내가 이동할 y 좌표),
int arr[][] // (미로 초기화),
BFS() 메서드 // 핵심 로직,
Queue<Integer> Q1// Level별 데이터 자료구조,
Queue<Integer> Q2// Level별 데이터 자료구조
핵심 문제 해석
첫째 최단 거리를 구할 때는 BFS를 사용하자
둘째 경로가 동서남북으로 뻗어갈 수 있다.
문제 풀이 과정
이번에는 코드를 작성할 때마다
이 코드가 미칠 영향, 방향성에 대해 상상해보았다.
즉, 논리적인 사고로 푼 것이다.
처음에는 rL + cL 값이 14가 되었을 때 L+1을 출력하는 방식으로 로직을 짜봤다.
하지만 현재 좌표가 어디인지 정보를 제공해주지 못하므로
접근을 달리했다.
Queue에 x좌표와 y좌표 정보가 필요했기에
Queue에 어떻게 x좌표와 y좌표를 담아서
어떤 방식으로 처리해줄지에 대해 고민했다.
그래서 Queue를 두개를 만들어서 각각 x좌표 y좌표로 초기화 한 다음 코드를 적어나갔다.
이 코드가 어떤 식으로 나아갈지 상상해봤을 때
정답에 다가가고 있다는 것을 알 수 있었다.
코드를 돌려보니 정답 값이 나왔다.
하지만 어딘가 내 코드에 문제점이 있을 수 있다.
그래서 디버그를 돌려보며 내 코드의 로직을 면밀히 살펴봤다.
최단 경로의 길이를 구하는 문제이기 때문에
첫 시작점에서 우 방향, 하 방향 두가지 방향으로 뻗어나가도
괜찮다고 생각했었고, arr[1][1] = 1을 선언해주지 않았었다.
그러자 다음 좌표에서 첫 시작점을 한번 더 방문한다는걸
디버그를 통해 알게되었다.
이는 불필요한 과정이기 때문에 arr[1][1] = 1을 선언해주었고 문제를 해결할 수 있게 되었다
핵심 코드
public int BFS(int rL, int cL){
Queue<Integer> Q1 = new LinkedList<>();
Queue<Integer> Q2 = new LinkedList<>();
int L = 0;
Q1.offer(rL);
Q2.offer(cL);
while(!Q1.isEmpty() && !Q2.isEmpty()){
int len = Q1.size();
for(int i = 0; i < len; i++){
int x = Q1.poll();
int y = Q2.poll();
for(int j = 0; j < 4; j++){
int nx = x+dx[j];
int ny = y+dy[j];
if(nx == 7 && ny == 7) return L+1;
if (nx > 0 && ny > 0 && nx <= 7 && ny <= 7 && arr[nx][ny] == 0) {
arr[nx][ny] = 1;
Q1.offer(nx);
Q2.offer(ny);
}
}
}
L++;
}
return -1;
}개선된 점
첫째 코드를 작성할 때마다 어떤 방향으로 나아가게될 지 상상하면서 코드를 작성했다.
즉, 논리적인 사고를 바탕으로 코드를 작성한 것이다.
지금 방향성이 옳은지,
내가 적은 코드의 방향성은 어떠한지,
정답으로 향하는 코드인지,
내가 문제를 잘못 접근하고 있는건 아닌지... 등
여러가지 경우를 고려하면서 문제를 풀었다.
둘째 디버그를 적극 활용했다.
결과가 정답이어도 과정이 정답이라는 보장이 없기에
내가 짠 코드의 과정이 내가 생각한대로 흘러가는지
살펴봐야할 필요가 있었다.
그래서 디버그를 돌려보았고
arr[1][1] = 1 코드를 추가해줌으로써 불필요한 과정까지
생략할 수 있었다.
느낀점
첫째 상상을 많이 하자!
인간의 두뇌에서 기타 동물들과 가장 다른 점은 미래 예측 능력이다.
미래 예측 능력은 상상할 수 있는 능력과 같다.
즉, 인간은 상상력이 강할 수록 똑똑한 사람이라고 봐도 무방하다고 생각한다.
그러니,
상상력을 키우자. 문제해결을 여러 방면으로 접근해보자.
