숙직 선생님

1. 문제

2. 문제분석

BFS 나 DFS는 항상 트리의 개념으로 이해를 해야 한다.

그리고, 위의 입력 예시와 같이 먼저, 선생님의 현재위치를 1로 고정시키고,

누군가의 위치를 15로 고정 시키자.

그러면 다음과 같이 될 것이다.

그리고 Tree의 개념으로 그림을 그려보자.

위의 그림에서 2, 5, 7이라는 붉은 상자안의 숫자의 의미는 선생님이 한 번에 이동할 수 있는

능력이다. 문제의 입력 예시 부분에서 볼 수 있다.

그리고, 위의 트리 구조에서 1은 선생님의 현재 위치이다.

즉, 선생님이 이동 할 수 있는 위치가 각 각 3,6,8 이라는 위치이다.

1 + 2 = 3

1 + 5 = 6

1 + 7 = 8

그리고, 3,6,8의 위치에서 다시 움직일 수 있는 위치는 아래와 같다.

3 + 2 = 5

3 + 5 = 8

3 + 7 = 10

​

​이 순서대로 계속 위치를 찾아 갈 수 있다.

즉, 누군가의 위치인 15에서 끊어주면 된다.

위의 탐색 함수를 구현하면 아래와 같다.

3. 구현

프로그램 실행결과

 

4. 소스 파일

main.c

0.00MB

 

5. 개선할 점

아래와 같이 탐색 함수에서 숙직 선생님의 이동 회수가 최소 회수보다 크면 바로 종료하고 다음 조건을 탐색한다.

어차피 이동 회수가 최소 회수보다 크면 목적지 위치에 도착하면 당연히 이동 회수가 최소 이동 회수보다 크다는 것은

자명하다.

애초에 탐색 시에 현재의 숙직 선생님의 이동 회수가 최소 이동 회수보다 크면 탐색을 종료하고

다음 탐색을 시도해서 연산량을 줄이는 것이 아이디어이다.

실행결과

 

6. 소스 파일

main.c

0.00MB