Hide and Seek4

문제 복기

내가 접근한 방법

어떤 수 k가 있을 때 cur+1 = k인지, cur-1=k인지, 2*cur=k인지 알아내야한다. 그래서 아래와 같이 구현했다.

if(cur-1==k) {
    ...
    System.out.print(cur+" ");
}
if(cur+1==k) {
    ...
    System.out.print(cur+" ");
}
if(2*cur==k) {
    ...
    System.out.print(cur+" ");
}

막혔던 부분

출력되는 순서와 코드상에서 실행되는 순서가 달라 결국 오답이 될 수밖에 없다.

코드 : 1. k가 되는 정점의 순서들은 dist배열이 생성되는 중에 나오기 때문에 먼저 나온다. 2. dist배열은 제일 마지막에 구현되어 dist[k]도 마지막에 나온다. 올바른 순서 : 1. dist[k] 2. k가 되는 정점 순서들

=>해결방법 : 애초에 dist배열을 완성할 때 a->b가 되는 것을 기록해준다! 이를 저장하는 배열을 하나 생성하여 from[b] = a 이렇게 저장해준다! a->b, c->b, d->b, e->b 등 b가 될 수 있는 a,c,d,e,f,g,...가 많을 때 from[b]에는 한가지 값만 저장할 수 있으므로 발상의 전환 : from[a] = b, from[c] = b, from[d] = b,..이렇게 처리해주면 한가지값에 대해 여러가지 값을 가질 수 있는 의미를 저장할 수 있다!

역추적 문제 푸는 방법

0. a가 b에 의해 바뀔 때 왜 바뀌었는지 기록해야한다.

1. m을 출력하는 재귀함수 이용 : from[m]->m 이므로 m을 from[m]으로 계속해서 갱신하여 함수를 호출해준다. 재귀함수 특징은 더이상 갈 수 없을 때까지 깊이 파고들기 때문에 초기값 n까지 호출되어 간다. 호출된 (n,m)에서 n과 m이 같아질 때까지 반복한다! 종료 조건 : n==m 반복 조건 : n!=m 이면 계속해서 재귀함수 호출!

2. 반복문과 스택 이용(스택의 성질 이용 : 역추적 문제에서 가장 바람직한 추적 방법) 반복문을 통해 끝에서부터 나오는 m을 스택에 넣고, 마지막에 n을 스택에 넣는다. 스택을 pop하면 n->m 이 되는 숫자들을 역순으로 출력할 수 있다! m값을 통해 from[m]으로 그 다음으로 추적할 값을 접근할 수 있다!

알게된 신박한 반복문 조건 일단 처음 m에서 시작해서 m을 계속해서 스택에 넣는다. 이 반복되는 m은 from 배열에서부터 다음 m값이 정해진다! ex)m=17->다음 m=from[17] : 다음 m=from[현재 m] 반복되는 m을 i라고 하면, i=m, i = from[i], i!=n 현재의 i(m)이 n과 같아지면 종료하는 거니까, i!=n인 동안 반복한다! => 스택:4 8 16 17 마지막에 스택에 초기값 n을 넣어주면 스택이 완성된다!

Stack<Integer> st = new Stack<Integer>();
		for(int i=m;i!=n;i=from[i]) {
			st.push(i);//m->from[m]->from[from[m]]
		}
		st.push(n);
		while(!st.isEmpty()) {
			System.out.print(st.pop()+" ");
		}