문제
- 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다.
- 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.
- 송아지는 움직이지 않고 제자리에 있다.
- 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.
- 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.
입력
- 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다.
출력
- 점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다.
입출력 예제
풀이방식
이번 문제는 이진트리, 큐, 재귀함수를(을) 사용하여 푸는 문제이다.
더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다.
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)
설계과정
1. 현수의 위치를 루트 노드로 하여 레벨이 0인 트리를 시작한다.
2. 경우의 수 3가지를 각각의 자식 노드로 하여 다음 레벨을 그린다.
3. 해당 레벨에 해당하는 모든 노드들을 큐에서 꺼내고 출력한다.
아래 그림을 통해 자세히 알아보자.
1. 현수의 위치인 '5' 를 루트 노드로 정하고, 앞으로 1, 뒤로 1, 앞으로 5를 각각의 조건으로 해서 총 3개의 자식 노드를 생성한다.
2. 레벨을 늘리며 계속해서 자식노드를 생성한다.
3. 단, 이미 노드의 값이 존재했었다면 다음에 나오는 값은 생략한다.
4. 이렇게 해서 송아지의 위치에 도달하게 되면, 해당 노드의 레벨을 출력한다.
풀이과정
1. 전역으로 변수와 배열, 큐를 선언한다.
- result : 최소 횟수를 저장할 변수이다.
- dis[ ] : 거리 값들을 배열로 저장한다.
- ch[ ] : 한번 Q에 넣은 값들은 다시 넣지 않기 위해 체크배열을 선언한다.
2. BFS 메소드를 작성한다.
- BFS란 너비 우선 탐색으로 루트 혹은 임의의 다른 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다.
3. 배열 ch[ ] 에 크기를 10001로 설정한다.
- 문제에서 배열의 크기가 10000까지이므로 1을 더해서 생성한다.
4. ch[S]에 1을 넣고, Q에 넣는다. 이 때 변수 L도 0으로 초기화한다.
- 출발지점인 S는 무조건 Q에 들어가므로 1로 값을 정해서 Q에 넣어준다.
- 1이란, Q에 들어가지 않은 값이므로 넣어도 된다는 것을 의미한다.
- 변수 L은 레벨을 의미하며, 여기에서는 최단 거리인 결과값이다.
5. Q가 비어있지 않으면 계속해서 도는 while 문을 선언한다.
6. Q의 크기를 저장하는 변수 len을 선언한다.
- len은 Q의 크기 즉, 각 레벨에 해당하는 노드의 개수를 의미한다.
7. 0부터 len까지 도는 for문을 통해 큐에서 값을 꺼내 x에 저장한다.
8. 0부터 3까지 도는 for문을 작성하여 자식노드를 만든다.
- j는 다음 레벨로, 자식 노드는 무조건 3개까지만 나오므로 3번만 돌게 한다.
9. nx에 x + dis[ j ] 한 값을 넣는다.
- nx : x의 자식노드이다.
- x 에 dis 배열의 값들을 각각 더해서 3개의 자식 노드를 생성한다.
10. 송아지 위치에 도달하면 L을 리턴한다
- nx 는 자식 노드이므로 L에서 1을 더해줘야한다.
- L = 노드의 레벨 = 거리
11. 해당 거리가 아직 Q에 저장된 적이 없으면 1을 넣고, Q에 저장한다.
해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.
