[백준/java] 1697번 : 숨바꼭질 - BFS

 

 

이번 문제는 2차원배열 위주로 풀던 BFS 문제를 폭넓은 시각으로 바라볼 수 있게 해주는 문제 같다.

 

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

1697번: 숨바꼭질

백준 1697번 숨바꼭질

 

입력값을

5 17

로 입력하면 출력값이 4로 나와야 한다.

 

출발값인 5를 제외한 17까지의 나머지 숫자 카운트가 4번이어야 한다.

 

문제의 조건대로 3가지의 조건. 수빈의 위치 + 1, 수빈의 위치 -1, 수빈의 위치 * 2 연산을 수행해야 한다.

 

public static int move(int pos, int idx) {
    int loc = pos;

    switch(idx) {
        case 1 : loc+=1; break;
        case 2 : loc-=1; break;
        case 3 : loc*=2; break;
    }

    return loc;
}

 

출발 위치 5로부터 동생의 위치인 17까지의 경로를 보면

5 -> 6, 5 -> 4, 5 -> 10 이런식으로 나오게 되는데

 

이런식으로 출력을 해보면

출발 위치 : 5, 옮긴 위치 : 6, 카운트 : 1
출발 위치 : 5, 옮긴 위치 : 4, 카운트 : 1
출발 위치 : 5, 옮긴 위치 : 10, 카운트 : 1
출발 위치 : 6, 옮긴 위치 : 7, 카운트 : 2
출발 위치 : 6, 옮긴 위치 : 12, 카운트 : 2
출발 위치 : 4, 옮긴 위치 : 3, 카운트 : 2
출발 위치 : 4, 옮긴 위치 : 8, 카운트 : 2
출발 위치 : 10, 옮긴 위치 : 11, 카운트 : 2
출발 위치 : 10, 옮긴 위치 : 9, 카운트 : 2
출발 위치 : 10, 옮긴 위치 : 20, 카운트 : 2
출발 위치 : 7, 옮긴 위치 : 14, 카운트 : 3
출발 위치 : 12, 옮긴 위치 : 13, 카운트 : 3
출발 위치 : 12, 옮긴 위치 : 24, 카운트 : 3
출발 위치 : 3, 옮긴 위치 : 2, 카운트 : 3
출발 위치 : 8, 옮긴 위치 : 16, 카운트 : 3
출발 위치 : 11, 옮긴 위치 : 22, 카운트 : 3
출발 위치 : 9, 옮긴 위치 : 18, 카운트 : 3
출발 위치 : 20, 옮긴 위치 : 21, 카운트 : 3
출발 위치 : 20, 옮긴 위치 : 19, 카운트 : 3
출발 위치 : 20, 옮긴 위치 : 40, 카운트 : 3
출발 위치 : 14, 옮긴 위치 : 15, 카운트 : 4
출발 위치 : 14, 옮긴 위치 : 28, 카운트 : 4
출발 위치 : 13, 옮긴 위치 : 26, 카운트 : 4
출발 위치 : 24, 옮긴 위치 : 25, 카운트 : 4
출발 위치 : 24, 옮긴 위치 : 23, 카운트 : 4
출발 위치 : 24, 옮긴 위치 : 48, 카운트 : 4
출발 위치 : 2, 옮긴 위치 : 1, 카운트 : 4
출발 위치 : 16, 옮긴 위치 : 17, 카운트 : 4
출발 위치 : 16, 옮긴 위치 : 32, 카운트 : 4
출발 위치 : 22, 옮긴 위치 : 44, 카운트 : 4
출발 위치 : 18, 옮긴 위치 : 36, 카운트 : 4
출발 위치 : 21, 옮긴 위치 : 42, 카운트 : 4
출발 위치 : 19, 옮긴 위치 : 38, 카운트 : 4
출발 위치 : 40, 옮긴 위치 : 41, 카운트 : 4
출발 위치 : 40, 옮긴 위치 : 39, 카운트 : 4
출발 위치 : 40, 옮긴 위치 : 80, 카운트 : 4
4

 

처럼 출력 된다.

 

그리고 영역이 유효한 영역인지 아닌지 확인하는 로직이 필요하다.

if(moveVal > 100000 || moveVal < 0) continue;

 

그리고 불필요한 방문을 방지하기 위해 visit 여부를 확인해주어야 한다.

if(visit[moveVal]) continue;

 

 

지금까지의 모든 코드를 정리해보면 아래와 같다.

package dfsAndBfs;

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

public class P1697_HideAndSeek {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Pos subin = new Pos(sc.nextInt());
		int sister = sc.nextInt();
		boolean[] visit = new boolean[100001];
		Queue<Pos> q = new LinkedList<Pos>();
		q.add(subin);
		visit[subin.loc] = true;
		
		int answer = 0;
		
		while(!q.isEmpty()) {
			Pos cur = q.poll();
			
			if(cur.loc == sister) {
				answer = cur.cnt;
				break;
			}
			
			for (int i = 1; i <= 3; i++) {
				int moveVal = move(cur.loc, i);
				
				if(moveVal > 100000 || moveVal < 0) continue;
				
				if(visit[moveVal]) continue;
				
				Pos temp = new Pos(moveVal, cur.cnt + 1);
				
//				System.out.println("출발 위치 : " + cur.loc + ", 옮긴 위치 : " + temp.loc + ", 카운트 : " + temp.cnt);
				
				visit[temp.loc] = true;
				
				q.add(temp);
			}
		}
		
		System.out.println(answer);
		sc.close();
	}
	
	public static int move(int pos, int idx) {
		int loc = pos;
		
		switch(idx) {
			case 1 : loc+=1; break;
			case 2 : loc-=1; break;
			case 3 : loc*=2; break;
		}
		
		return loc;
	}
	
	static class Pos {
		int loc, cnt;
		
		public Pos(int loc) {
			this.loc = loc;
			this.cnt = 0;
		}
		
		public Pos(int loc, int cnt) {
			this.loc = loc;
			this.cnt = cnt;
		}
	}
}