[JAVA] 1697번 - 숨바꼭질

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

일단 최소 이동횟수를 구해야하기 때문에 bfs문제이다.

두가지 방법으로 풀어보았다

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. 첫번째 방법

큐에 직접적으로 이동 횟수를 추가하는 방법이다.

 

1. int[] 형태의 큐를 선언한다. 각각 수빈이의 현재위치, 수빈이의 이동횟수가 될 것이다.

2. 큐에 삽입한다 (최초 삽입의 경우 {n,0}을 넣어야한다. 수빈이의 위치에서 시작할것이고, 이동횟수는 0이기때문

3. 최초 시작 위치를 방문처리한다(이건 꼭 해야한다, 방문처리 안하면 무한루프 발생하는걸 코드를 짜면서 깨달음)

4. while문 실행

5. 큐의 값을 꺼내서 각 변수에 현재 위치, 이동횟수를 넣는다

6. 종료조건 걸어준다 -> 현재위치가 k라면 도착한거니까 이동횟수를 반환하고 종료

--이제 여기서부터는 3가지 분기가 나온다. 이동할 수 있는 경우의 수가 3개이기 때문이다--

7. 수빈이가 이동했을때 위치를 계산한다

int go = now+1;

8. 범위 초과하지않고, 방문한 곳이 아니라면 갈 수 있기때문에, 방문처리를하고, 큐에 추가한다

if(go <= 100000 && !visited[go] ) { //새로운 이동위치가 방문하지 않고 범위초과안한다면
				visited[go] = true;
				q.add(new int[] {go,cnt+1});
			}

 

1. 두번째 방법

배열 자체에 이동 횟수를 넣어주는 방법이다.

 

1. Integer 형태의 큐를 선언한다.  수빈이의 현재위치가 될 것이다.

2. 큐에 삽입한다 (최초 삽입의 경우 n을 넣어야한다. 수빈이의 위치에서 시작할것이기때문

3. 최초 시작 위치를 방문처리한다(이건 꼭 해야한다, 방문처리 안하면 무한루프 발생하는걸 코드를 짜면서 깨달음)

4. while문 실행

5. 큐의 값을 꺼내서  변수에 현재 위치를 넣는다

6. 종료조건 걸어준다 -> 현재위치가 k라면 도착한거니까 이동횟수를 반환하고 종료

--여기서부터 첫번재 방법과 다르다--

7. for문을 걸어준다(이동할 수 있는 방법이 3가지라서 미리 배열을 만들어둔것이다 4방향이동처럼 for문걸어주는것)

 pos = new int[] {1,-1,2};

이렇게 미리만들었다.

여기서는 2곱하기와 더하기로 나뉘므로 두가지 분기를 나눔

9. pos[i]의 값이 2일경우 -> next의 위치(다음 수빈이가 이동할 위치)는 현재 위치 *2다

10. 나머지는 +1이거나 -1이다.

11. 범위초과하지 않고, 방문하지 않았다면 -> 방문처리를 하고, 큐에 삽입

12. 배열에서 수빈이가 다음 이동한 next에 arr[now]+1을더한다.

-> 배열 자체에 이동횟수를 넣어주는 것이다. 현재 위치 now에서 한번 이동한것이니까 +1값을 새로 도착하는 위치 next에 더해주는것

for(int i=0; i<3; i++) {
				int next;
				
				if(pos[i]==2) {
					next= now*pos[i];
				}
				else {
					next = now+pos[i];
				}
				
				if(next<=100000 && next>=0 && !visited[next]) {
					visited[next] = true;
					q.add(next);
					arr[next] = arr[now]+1;
				}
				
			}

 

 

 

 

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

1.첫번째 방법으로 푼 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.*;
import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Main {
	static int n,k;
	static int []arr;
	static boolean[] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        
        arr = new int[100001];
        visited= new boolean[100001];
        
        System.out.println(bfs());
        
        
    }
	private static int bfs() {
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] {n, 0});
		visited[n] = true;
		
		while(!q.isEmpty()) {
			int[] tmp=q.poll();
			int now=tmp[0]; //수빈이의 현 위치
			int cnt = tmp[1]; //수빈이의 이동 횟수 
			
			if(now==k) {
				return cnt;
			}
			
			int go = now+1;
			if(go <= 100000 && !visited[go] ) { //새로운 이동위치가 방문하지 않고 범위초과안한다면
				visited[go] = true;
				q.add(new int[] {go,cnt+1});
			}
			
			int back = now-1;
			if(back >= 0 && !visited[back] ) { //새로운 이동위치가 방문하지 않고 범위초과안한다면
				visited[back] = true;
				q.add(new int[] {back,cnt+1});
			}
			
			int jump = now*2;
			if(jump <= 100000 && !visited[jump] ) { //새로운 이동위치가 방문하지 않고 범위초과안한다면
				visited[jump ] = true;
				q.add(new int[] {jump ,cnt+1});
			}
			
		}
		return -1;
	}
	

}

 

 

2.두번째 방법으로 푼 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.*;
import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Main {
	static int n,k;
	static int []arr;
	static boolean[] visited;
	static int[] pos;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        
        arr = new int[100001];
        visited= new boolean[100001];
        pos = new int[] {1,-1,2};
        
        bfs();
        
        
    }
	private static void bfs() {
		Queue<Integer> q = new LinkedList<>();
		q.add(n);
		visited[n] = true;
		
		while(!q.isEmpty()) {
			int now = q.poll(); //수빈이의 현재 위치 
			
			if(now==k) {
				System.out.println(arr[now]);
			}
			
			for(int i=0; i<3; i++) {
				int next;
				
				if(pos[i]==2) {
					next= now*pos[i];
				}
				else {
					next = now+pos[i];
				}
				
				if(next<=100000 && next>=0 && !visited[next]) {
					visited[next] = true;
					q.add(next);
					arr[next] = arr[now]+1;
				}
				
			}
			
			
		}
		
	}
	

}