Q7 - 8 송아지 찾기(BFS : 상태트리탐색)

2021. 11. 8. 21:59·코딩 테스트/7. Recursive, Tree, Graph
728x90
반응형

8. 송아지 찾기 1(BFS : 상태트리탐색)

 

* 설명

현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다.

현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다.

현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.

최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.

 

* 입력

첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다.

* 출력

점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다.

 

* 예시 입력 1 

5 14

* 예시 출력 1

3

 

 

 

 

 

package Q7.Test8;//송아지 찾기(BFS : 상태트리탐색)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	int[] dis = {1, -1, 5};
	int[] ch; //한 번 방문 한 곳은 또 다시 방문 하지 않기 위한 체크 배열
	Queue<Integer> Q = new LinkedList<Integer>();//정수 저장
	public int BFS(int in1, int in2) {
		ch = new int[10001]; //1부터 10000까지니까
		
		ch[in1] = 1; //출발 지점
		Q.offer(in1);
		
		int L = 0; //루트 노드의 지점
		
		while(!Q.isEmpty()) {
			int len = Q.size();//레벨의 길이
			for(int i = 0; i < len; i++) {
				int x = Q.poll();
//				방법 1
//				if(x==in2) {
//					return L;
//				}
				for(int j = 0; j < 3; j++) {
					int nx = x+dis[j]; //nx = 자식 노드
					
//					방법2
					if(nx == in2) {
						return L+1;//자식노드니까 +1
					}
//
					
					if(nx>=1 && nx <= 10000 && ch[nx]==0) {
						ch[nx] = 1;
						Q.offer(nx);
					}
				}
			}
			L++;
		}
		return 0;
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner in = new Scanner(System.in);
		int in1 = in.nextInt();//현수 위치
		int in2 = in.nextInt();//송아지 위치
		System.out.println(T.BFS(in1, in2));

	}

}
728x90
반응형

'코딩 테스트 > 7. Recursive, Tree, Graph' 카테고리의 다른 글

Q7 - 7 이진트리 순회(넓이우선탐색=레벨탐색=BFS)  (0) 2021.11.11
Q7 - 6 부분집합 구하기(DFS)  (0) 2021.11.08
Q7 - 5 이진트리 순회(깊이 우선 탐색  (0) 2021.11.08
Q7 - 4 피보나치 수열  (0) 2021.11.08
Q7 - 3 팩토리얼  (0) 2021.11.08
'코딩 테스트/7. Recursive, Tree, Graph' 카테고리의 다른 글
  • Q7 - 7 이진트리 순회(넓이우선탐색=레벨탐색=BFS)
  • Q7 - 6 부분집합 구하기(DFS)
  • Q7 - 5 이진트리 순회(깊이 우선 탐색
  • Q7 - 4 피보나치 수열
길동이이이잉
길동이이이잉
길동이이이잉
코딩 일기
길동이이이잉
코딩 일기일까......?
삽질...... 일기일까?
반응형
250x250
  • 모든 글 (97)
    • 개발일기 (9)
      • Project (9)
      • React (1)
      • DB, SQL (7)
      • Spring (5)
      • AWS (1)
    • 코딩 테스트 (63)
      • 1. String(문자열) (12)
      • 2. Array(1, 2차원 배열) (12)
      • 3. Tow pointers, Sliding wi.. (6)
      • 4. HashMap, HashSet, TreeSe.. (5)
      • 5. Stack, Queue (8)
      • 6. Sorting and Searching (8)
      • 7. Recursive, Tree, Graph (11)
      • 8. DFS, BFS 활용 (0)
      • 9. ... (1)
    • 갔다왔다 워홀! (2)

인기 글

태그

유럽
s3대용량업로드
Strategic Design
Tactical Design
AWS
reactnative
aws업로드
전략적 설계
spring
달력프로젝트
Oracle
s3대용량파일업로드
아일랜드워홀
유럽워홀
전술적 설계
워홀
React
SpringBoot
워킹홀리데이
아일랜드

최근 글

hELLO· Designed By정상우.v4.5.3
길동이이이잉
Q7 - 8 송아지 찾기(BFS : 상태트리탐색)

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.