코테 | 강의 - 너비 우선 탐색 - BFS 섹션 - (1)

⬛ 너비 우선 탐색 | BFS

🟩 1번. 타일 점프 | BFS

풀이

• 이 문제는 레벨 탐색 문제이다.
• 각 레벨에서 방문 가능한 정점들을 큐에 담아서 차례로 방문하는 방식으로 인접 정점 우선으로 처리한다.
• Q에는 각 레벨별로 닿을 수 있는 정점들이 존재할 것이므로 for문으로 그 정점들을 순회한다.
• 해당 정점 x에 대하여 다시 for 문을 돌면서 x가 가진 최대 점프 횟수까지를 차례로 순회한다.
• nx 정점이 우리가 찾는 도착지 직전값이면 return lv++ 하여 리턴하면 되고
• nx 정점이 아직 n보다 작으면서 방문한 적 없을 경우에는 방문 처리하면 된다.

→ 이 사이클에 대하여 lv++ 처리하면서 각 레벨에 대해 방문 가능한 인접 정점들을 우선 방문하면서 최소 점프횟수로 도착지에 갈 수 있는 방법을 찾는 문제이다.

package to_0816_4;
import java.util.*;
//타일점프 RE
class Solution {
	//solution
	public int solution(int[] nums){
		int n = nums.length;
		boolean[] ch = new boolean[n];//방문 체크
		Queue<Integer> Q = new LinkedList<>();
		//시작점 처리
		Q.add(0);
		ch[0] = true;
		int lv = 0;
		
		while(!Q.isEmpty()) {
			int len = Q.size();
			//-> 현재 레벨에서 갈 수 있는 == 큐에 존재하는 모든 좌표 순회할 거임 
			for(int i=0; i<len; i++) {
				int x = Q.poll();//현재 정점
				for(int j=1; j<=nums[x]; j++) { //현재 정점에서 점프 가능한 다음 정점 순회용
					int nx = x + j;//다음 정점

					if(nx == n-1) return lv+1;					
					if(nx < n && !ch[nx]) {
						ch[nx] = true;
						Q.add(nx);
					}
				}
			}
			lv++; //다음 레벨로 이동
		}
		
		return -1;
	}
	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(new int[]{2, 2, 1, 2, 1, 1}));
		System.out.println(T.solution(new int[]{1, 0, 1, 1, 3, 1, 2, 1}));
		System.out.println(T.solution(new int[]{2, 3, 1, 0, 1, 1, 2, 3, 1, 5, 1, 3, 1}));
		System.out.println(T.solution(new int[]{1, 2, 1, 2, 1, 2, 1, 1, 3, 1, 2, 1}));
		System.out.println(T.solution(new int[]{1, 3, 2, 1, 1, 2, 3, 1, 3, 1, 2, 3, 5, 1, 5, 1, 2, 1, 1}));
	}
}

---

🟩 2번. 집으로 이동 | BFS

풀이

• 2차원 배열로 ch[2][10001] 선언해서,
• ch[0][nx] 는 앞으로 이동해서 nx를 방문. ch[1][nx] 는 뒤로 이동해서 nx를 방문했다는 식으로 방문 처리를 할 것이다.
• 1) 웅덩이는 방문 불가능하므로 애당초 방문 체크시켜둔다.
• 2)  b의 경우 두번이상 연속 불가능하므로, 직전에 방문한 cur[1] 의 값이 0일 때에만 (=앞으로 이동) b에 대해서도 점프 가능하도록 설정한다.
• → 큐에는 <nx, 앞/뒤>이런 식으로 값이 들어가기 때문에
• cur[0]번째 값인 nx는 방문하는 정점이 되고
• cur[1]번째 값은 0 : +a로 온 경우, 1: -b로 온 경우 이렇게 나누어 처리한 것이다.

package to_0816_7;
//집으로 가자 RE 풀이 
import java.util.*;
class Solution {
	//솔루션 
	public int solution(int[] pool, int a, int b, int home){
		boolean [][] ch = new boolean[2][10001];
		for(int x : pool) {
			ch[0][x] = true;
			ch[1][x] = true;
		}
		
		Queue<int[]> Q = new LinkedList<>();
		//시작점 처리 
		ch[0][0] = true;
		ch[1][0] = true;
		Q.add(new int[] {0, 0});
		int lv = 0;
		while(!Q.isEmpty()) {
			int len = Q.size();
			for(int i=0; i<len; i++) {
				int[] cur = Q.poll();
				//큐에는 <좌표, 왼오> 식으로 값이 들어있기 때문에
				//cur[0] 은 좌표값
				//cur[1]에는 0 또는 1의 값이 들어있음
				//-> 0인 경우 +a로 온 값, 1인 경우 -b로 온 값인데
				//여기서 뒤쪽 b로는 두 번이상 연속 점프 불가능 함
				if(cur[0] == home) return lv;
				//cur[0]은 앞에서 온애, cur[1] 은 뒤에서 온애
				int nx = cur[0] + a;
				if(nx <= 10001 && !ch[0][nx]) {
					ch[0][nx] = true;
					Q.add(new int[] {nx, 0});
				}
				nx = cur[0] - b;
				 //cur[1] == 0 : <nx, 앞-뒤>이런 식으로 들어오는데 , 즉, cur[1] 직전에 앞으로 온 좌표에 한해서 nx로 b점프 가능이란 뜻.
				if(nx >=0 && !ch[1][nx] && cur[1] == 0) { //따라서 직전 점프가 0 (앞에서 온 경우에만) b로 점프 가능함
					ch[1][nx] = true;
					Q.add(new int[] {nx, 1});
				}
			}
			lv++;
		}
		return -1;
	}
	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(new int[]{11, 7, 20}, 3, 2, 10));	
		System.out.println(T.solution(new int[]{1, 15, 11}, 3, 2, 5));	
		System.out.println(T.solution(new int[]{9, 15, 35, 30, 20}, 2, 1, 25));	
		System.out.println(T.solution(new int[]{5, 12, 7, 19, 23}, 3, 5, 18));	
		System.out.println(T.solution(new int[]{10, 15, 20}, 3, 2, 2));	
	}
	
}

 

RE 풀이 

- cur[0] 을 dx현재 좌표로

- cur[1]을 ctr 점프 정보 컨트롤 로 두고 다시 풀이함

package to_0816_8;
//집으로 가자 | RE 또 풀이
import java.util.*;
class Solution {
	//솔루션 함수 
	public int solution(int[] pool, int a, int b, int home){
		int[][] ch = new int[2][10001];
		for(int x : pool) {
			ch[0][x] = 1;
			ch[1][x] = 1;
		}
		
		Queue<int[]> Q = new LinkedList<>();
		ch[0][0] = 1;
		ch[1][0] = 1;
		Q.add(new int[] {0, 0});
		
		int lv = 0;
		while(!Q.isEmpty()) {
			int len = Q.size();
			for(int i=0; i<len; i++) {
				int[] cur = Q.poll();
				int dx = cur[0];//좌표 정보
				int ctr = cur[1];//0 or 1 점프 정보
				
				if(dx == home) return lv;//여기서 정답체크
				//1) a로 점프하기 
				int nx = dx + a;
				if(nx <= 10001 && ch[0][nx] == 0) {
					ch[0][nx]  = 1;//앞으로 갔다고 체크
					Q.add(new int[] {nx, 0});
				}
				
				//2) b로 점프하기
				nx = dx - b;
				if(nx >= 0 && ch[1][nx] == 0 && ctr == 0) {
					ch[1][nx] = 1;
					Q.add(new int[] {nx, 1});
				}
			}
			//레벨 플플
			lv++;
		}
		return -1;
	}

	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(new int[]{11, 7, 20}, 3, 2, 10));	
		System.out.println(T.solution(new int[]{1, 15, 11}, 3, 2, 5));	
		System.out.println(T.solution(new int[]{9, 15, 35, 30, 20}, 2, 1, 25));	
		System.out.println(T.solution(new int[]{5, 12, 7, 19, 23}, 3, 5, 18));	
		System.out.println(T.solution(new int[]{10, 15, 20}, 3, 2, 2));	
	}
}

---

🟩 3번. 송아지를 잡자 | BFS

• 레벨 탐색을 해야 하는데, 전체를 완전히 탐색해버리면 시간초과가 나기 때문에 규칙성을 발견해야 한다.
• 현수는 <x+1>, <x-1>, <x*2> 식으로 점프를 할텐데, +1 → -1 식의 방문을 하게 되면 홀수 lv에서의 값들이 반복되는 것을 볼 수 있다.
• ch[2][정점] 으로 체크배열 선언하고,
• 짝수 레벨의 방문 정점은 ch[0][정점],
• 홀수 레벨의 방문 정점은 ch[1][정점] 으로 체크한다.

package to_0818_1;
/*송아지를 잡자- BFS 레벨 탐색
 * 이 문제는 모든 레벨을 다 탐색해버리면 시간초과가 나버리기 때문에 시간복잡도 줄여야 함
 * [규칙성 발견] : 반복되는 부분은 빼기 
 * 홀수 레벨에서 나타났던 값은 다시 홀수 레벨에서 나타난다.  
 * 따라서 짝수 레벨 위주로 볼 것 */
import java.util.*;
class Solution {
	//솔루션 함수 
	public int solution(int s, int e){
		//ch[0][w] : 짝수 레벨에서 방문하는 지점 체크
		//ch[1][w] : 홀수 레벨에서 방문하는 지점 체크
		int[][] ch = new int[2][200001];
		Queue<Integer> Q = new LinkedList<>();
		//시작점 초기화 - 0레벨에서의 시작점 초기화 - 짝수이므로 0에 s 체크
		int lv = 0;
		ch[0][s]= 1;
		Q.offer(s);
	
		while(!Q.isEmpty()) {
			lv++;//다음 레벨 
			int len = Q.size();
			for(int i = 0; i<len ;i++) {
				int x = Q.poll();
				for(int nx : new int[] {x-1, x+1, x*2}) {
					if(nx >= 0 && nx <= 200000 && ch[lv%2][nx] == 0) {
						ch[lv%2][nx] = 1;
						Q.offer(nx);
					}
				}
			}
			e = e + lv;
			if(e > 200000) return -1;
			if(ch[lv%2][e]==1) return lv;
		}
		return -1;
	}
	//실행 메인 
	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(1, 11));	
		System.out.println(T.solution(10, 3));	
		System.out.println(T.solution(1, 34567));
		System.out.println(T.solution(5, 6));	
		System.out.println(T.solution(2, 54321));	
	}
}