[코딩테스트] bfs

April 12, 2021

reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.

BFS

BFS의 목적은 임의의 정점에서 시작해서, 모든 정점을 한 번씩 방문하는 것 (DFS 목적도 같음)
BFS는 모든 가중치가 1일 때 최단 거리를 구하는 알고리즘. (가중치 1 아닐때는 dijkstra 이용)

문제의 상황으로 그래프 그릴 수 있다.
최소 비용 문제여야 한다
간선의 가중치가 1이어야 한다
정점과 간선의 개수가 적어야 한다(적다 = 문제의 조건에 맞춰 해결할 수 있다. 시간 복잡도가 O(V+E)기 때문임!)

간선의 가중치 = 문제에서 구하는 최소의 비용 의미와 같아야함. (거리 최소값이면 가중치 거리, 시간 최소값이면 가중치 시간)

숨바꼭질 (1697번)

문제

수빈이 위치 N
동생 위치 K
동생을 찾는 가장 빠른 시간 구하는 문제
수빈이가 할 수 있는 행동 (위치:X)

걷기 X+1 또는 X-1로 이동(1초)
순간이동 2*X로 이동(1초)

풀이

위치 정점, 이동은 간선. 그래프로 표현 가능하다.
간선의 의미는 행동(1초 걸린다) = 가중치 1로 같음, 또한 가장 빠른 시간을 구하는 것이기에 목적도 같음. n,k <= 10만이기에 정점 M개, 간선 3M개 -> O(V+E) = 40만 정도 나오기 때문에 bfs 가능!
1~10만까지 가능한가? 갈 수 있는 곳 제한(경계값)은 한 20만정도…(-1로 10만간다고 가정)
check[i] = i를 방문했는지, dist[i]= i를 몇 번만에 방문했는지

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		final int MAX = 200000;
		Queue<Integer> q = new LinkedList<Integer>();
		boolean[] check = new boolean[MAX];
		int[] dist = new int[MAX];

		check[n] = true;
		dist[n] = 0; //시작점은 0으로 처리한다고 문제에서 말함
		q.add(n);

		while(!q.isEmpty()) {
			int x = q.remove();
			if(x-1>=0) {
				if(check[x-1]==false) {
					check[x-1]=true;
					dist[x-1] = dist[x]+1;
					q.add(x-1);
				}
			}
			if(x+1<MAX) {
				if(check[x+1]==false) {
					check[x+1]=true;
					dist[x+1]=dist[x]+1;
					q.add(x+1);
				}
			}
			if(2*x<MAX) {
				if(check[x*2]==false) {
					check[x*2]=true;
					dist[x*2] = dist[x]+1;
					q.add(x*2);
				}
			}
		}
		System.out.println(dist[k]);
	}
}

-> MAX값 구하는 것 같이 꼼꼼하게 문제를 봐야할 것 같다. 그래야 히든테케에서 안걸리지^_ㅠ

숨바꼭질 4 (13913번)

문제

수빈이 위치 N
동생 위치 K
동생을 찾는 가장 빠른 시간과 이동하는 방법을 구하는 문제
수빈이가 할 수 있는 행동 (위치:X)

걷기 X+1 또는 X-1로 이동(1초)
순간이동 2*X로 이동(1초)

풀이

대부분 문제의 역추적은 알고리즘이 달라져도 비슷하다. 하나의 값이 다른 값에 의해 변경되었고, 그게 필요하기 때문.
dp에서 LIS 점화식은 D[i] = max(D[j])+1 조건 j < i, A[j] < A[i] 였고 V[i] = j에 기록. 여기도 비슷함.

now -> next 라면

if(check[next]==false){
	q.push(next);
	check[next] = true;
	dist[next] = dist[now] + 1;
}

from[i]는 어디에서 왔는지 역추적. from[next] = now;

from[k2] -> from[k] -> k… 역순으로 저장되기 때문에 다시 역순으로 구해야 함.

재귀

void print(int n, int m){ //n->m으로 가는 방법 출력
	if(n!=m){
		print(n, from[m]); //앞쪽부터 출력하고
	}
	cout << m << ' '; //m출력
}

반복문 (스택)

stack<int> ans; //그냥 리스트여도 됨. 값을 순서대로 저장할 수 있는..
//하지만 N개의 순서를 뒤집는 가장 멋진 방법은 스택이다!
for(int i=m; i!=n; i=from[i]){
	ans.push(i);
}
ans.push(n);
while(!ans.empty()){
	cout << ans.top() << ' ';
	ans.pop();
}
cout << '\n';

자바 풀이

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		final int MAX = 200000;
		Queue<Integer> q = new LinkedList<Integer>();
		boolean[] check = new boolean[MAX];
		int[] dist = new int[MAX];
		int[] from = new int[MAX];

		check[n] = true;
		dist[n] = 0; //시작점은 0으로 처리한다고 문제에서 말함
		q.add(n);

		while(!q.isEmpty()) {
			int x = q.remove();
			if(x-1>=0) {
				if(check[x-1]==false) {
					check[x-1]=true;
					dist[x-1] = dist[x]+1;
					from[x-1] = x;
					q.add(x-1);
				}
			}
			if(x+1<MAX) {
				if(check[x+1]==false) {
					check[x+1]=true;
					dist[x+1]=dist[x]+1;
					from[x+1] = x;
					q.add(x+1);
				}
			}
			if(2*x<MAX) {
				if(check[x*2]==false) {
					check[x*2]=true;
					dist[x*2] = dist[x]+1;
					from[x*2] = x;
					q.add(x*2);
				}
			}
		}
		System.out.println(dist[k]);

		Stack<Integer> ans = new Stack<>();
		for(int i=k; i!=n; i=from[i]) {
			ans.push(i);
		}
		ans.push(n);
		while(!ans.isEmpty()) {
			System.out.print(ans.pop() + " ");
		}
		System.out.println();
	}
}

-> 고급지게 역순으로 표현하는 스택 기억하자,,!

[코딩테스트] bfs

BFS

숨바꼭질 (1697번)

숨바꼭질 4 (13913번)

댓글남기기

최근 포스트

[코딩테스트] 그래프의 탐색

210406 TIL

[코딩테스트] 그래프의 표현

[코딩테스트] 그래프