[백준 알고리즘]1697번: 숨바꼭질_Java

[문제]

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

[입력]

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

[출력]

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

[예제]

[힌트]

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

---

>문제 풀이

 입력값은 N과 K모두 0≤N, K≤100000 이기 때문에 mat, visited 배열 범위를 맞춰서 선언해준다.

그리고 N부터 -1, +1, 2*N 해가면서 K까지 가기위한 최단 거리를 구하면 된다.

 

최단 거리를 구할 땐? BFS !

N부터 시작해서 -1, +1, *2 한 값이 범위 안에 있고 방문한 적이 없으면

=> visited[nx] 방문처리, mat[nx]=mat[x]+1 카운팅 , 큐에 nx넣어주기

 

말은 쉽지만, 난 두번이나 틀렸었다...ㅋㅋㅋㅋㅎㅎ

처음에는 *2를 해주기 위해 dx={-1, 1, x}로 배열에 담아서 처리했었는데 dx[2]값을 갱신해주지 않아서 한 번 틀렸었고, 경계값 처리를 안해줘서 또 한 번 틀렸었다. (N==K가 입력될 경우를 잘 생각하길 바란다.)

 

>전체 코드

 

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

public class Main {
	static int N, K;
	static int visited[], mat[];
	
	public static void main(String [] args) {
		
		Scanner scan= new Scanner(System.in);
		
		N= scan.nextInt();
		K= scan.nextInt();
		visited= new int[100001];
		mat= new int[100001];
		
		mat[N]=1;
		
		bfs(N);
		if(N==K) mat[K]=1;
		System.out.println(mat[K]-1);
	}
	
	public static void bfs(int x) {
		int nx;
		int dx[]= {-1, 1, 0};
		Queue<Integer> que= new LinkedList<Integer>();
		
		que.offer(x);
		visited[x]=1;
		
		while(!que.isEmpty()) {
			x=que.poll();
			dx[2]=x;
			for(int i=0; i<3; i++) {
				nx= x+dx[i];
				if(nx==K) {
					mat[nx]=mat[x]+1;
					return;
				}
				if(0<=nx&&nx<mat.length&&visited[nx]!=1) {
					visited[nx]=1;
					mat[nx]= mat[x]+1;
					que.offer(nx);
				}//if
			}
		}//while
	}//bfs
	
}

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

 

 

 

 

+)이사했는데, 높은 책상은 있지만 아직 의자가 안왔고, 푹신한 방석은 있지만 좌식책상이 안와서 땅바닥에서 노트북을 두드리자니 목과 허리, 손목이 나가는 느낌이 든다...ㅋㅋㅋ;;;

뭘 쓸 수도 없고, 노트북으로 타자를 칠 수도... 즉, 공부를 할 수가 없다...;ㅅ;

내일 좌식책상이 온다고 했는데, 제발 빨리 왔으면 좋겠다...

할게 많은데 책상이 없으니 정리가 안되는 느낌이다.(´。＿。｀)