[JAVA]BOJ(백준) - 숨바꼭질 - 1697

- 문제 내용

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

---

- 문제 접근 방법

개인적으로 너무너무 아쉬운 문제다... 알고리즘 문제 풀때 1~2시간 고민하고 답안보이면 다른 분들 풀이를 참고하는 편인데 이건 내능력으로 충분히 풀수 있는 문젠데 생각하지 못해서 다풀지 못한문제다..ㅠ

 

문제를 풀기위해 가장먼저 생각한건 수빈(N)의 위치와 동생(K)의 위치가 처음부터 같다면 0을 출력. 만약 수빈이의 위치가 동생 위치보다 크다면 무조건 -1로밖에 못움직이기 때문에 N-K를 출력하는 것이다.

그리고 수빈(N)의 위치 < 동생(K)의 위치 일때 그냥 수학계산으로 할려고 했는데 말도 안되는 생각이였고, 먼저 BFS를 사용해 보기로 했다. BFS를 사용할때 상하좌우를 생각할때 처럼 +1, -1, *2의 경우로 나눠서 위치들을 계산하고 그위치를 큐에 넣는 방식으로 풀 생각을 했다.

그리고 일수를 계산하기 위해서 어떻게 해야할까 고민을 1~2시간했는데....전에 풀었던 미로탐색, 토마토 문제들처럼 정수형 배열을 만들고 수빈이가 현재위치에서 다음위치를 갈때마다 1을 증가시켜주면 되는거였는데 이걸 생각못하고 삽질을 오지게했다ㅠ

 

---

- 풀이

package org.boj.dfs.bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_1697 {
	static int N,K;
	static int[] dx = {1, -1, 2}; // 조건
	static int[] check; // 방문 배열이자 최소일수를 알려주는 배열
	
	public void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(N);
		
		while(!queue.isEmpty()) {
			int nowN = queue.poll();
			
			for(int i=0; i<3; i++) {// 1, -1, *2 했을때 경우로 나눔.
				int nextN;
				
				if(i==0 || i==1) {
					nextN = nowN+dx[i];
				}else {
					nextN = nowN*dx[i];
				}
				
				if(nextN>=0 && nextN<check.length && check[nextN]==0) { //다음 위치는 이조건을 만족해야함.
					check[nextN]=check[nowN]+1;
					queue.add(nextN);
				}
				
				if(nextN==K) { //다음 위치가 K(동생)위치와 같으면 현재 위치값에 +1하고 출력.
					System.out.println(check[nowN]+1);
					return;//함수 끝냄.
				}
			}//for
		}//while
	}//bfs
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		check = new int[100001];//올수있는 위치의 수만큼을 크기로 설정
		
		if(N==K) {//위치가 첨부터 같으면 0일
			System.out.println(0);
		}else if(N>K) {//N이 K보다 크면 무조건 -1을 해야됨. 그래서 N-K 출력
			System.out.println(N-K);
		}else {//N<K 일때는 이제 BFS 돌리면서 몇일걸리는지 구하기
			new BOJ_1697().bfs();
		}
	}
}

주의할점은 nextN의 값은 위치(인덱스)이기 때문에 무조건 0이상, check.length>nextN 이어야 한다. 그리고 중복방문해서 일수를 증가시는것을 피하기위해 방문안한(check배열 요소값=0)곳만 가도록 조건문을 줘야한다.

 

그리고 check의 크기를 100001로 한 이유는 인덱스는 0으로 시작하기 때문. 100000번째 자리를 위해서라고 생각하면된다.

---

- 마치며

충분히 풀수 있는 문젠데.. check배열하나만 생각해냈으면 되는 문제였는데 1~2시간동안 삽질하면서 못푼게 너무 아쉬운 문제였다. 이문제는 풀고나니 아직 많이 부족하다는걸 깨닳게 해주는 문제였다. 열심히 공부합시다!

 

아 그리고 dfs로 풀려고도 해봤는데 스택오버플로가 나서 못풀었다..ㅎㅎ 이문제에서 dfs는 방법이아닌듯,,? 물론 개인적인 생각임