[백준] DFS, BFS 사용 문제들

👋 DFS, BFS를 사용한 문제에서 생각할 수 있는 방법들을 알아보자! (TIL 231129)

2차원 배열에서 한 칸씩 탐색하는 경우

DFS나 BFS를 사용하는 문제에서는 2차원 배열 자료구조가 사용되는 경우가 많다.
탐색을 할 때는 보통 서로 인접한 칸으로만 이동할 수 있다는 조건이 붙기 때문에 상, 하, 좌, 우 4가지 방향으로 이동이 가능하다. 이 4가지 경우를 dx, dy 배열과 조건문을 통해 구현할 수 있다.

int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

for (int i=0; i<4; i++) {
	int nx = x + dx[i];
    int ny = y + dy[i];
}

구해야하는 것에 대한 배열을 sub로 둘 것

A -> B로 가는 최단 거리를 구해라 : distance 배열
DFS나 BFS에서는 특정 최대/최소값을 구하기 위해 push가 일어날 때 마다 갱신되는 값들을 저장해줄 공간이 필요하기 때문에 주로 배열을 sub로 설정한다.

디테일 놓치지 말기!

백준 1679번

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

queue<int> q;
int result = 0;
int x[100001] = {0, };

int bfs(int os, int ys) {
    
    if (os == ys ) return 0;
    
	q.push(os);
	x[os] = 0;
    
	while (!q.empty()) {
		int now = q.front();
		q.pop();

		if (now - 1 == ys || now + 1 == ys || 2 * now == ys) {
			x[ys] = x[now] + 1;
			break;
		}
		if (now - 1 >= 0 && x[now - 1] == 0) {
			q.push(now - 1);
			x[now - 1] = x[now] + 1;
		}
		if (now + 1 <= 100000 && x[now + 1] == 0) {
			q.push(now + 1);
			x[now + 1] = x[now] + 1;
		}
		if (2*now <= 100000 && x[2*now] == 0) {
			q.push(2*now);
			x[2*now] = x[now] + 1;
		}
	}

	return x[ys];
}

int main() {
	int os, ys; //older sister 언니 위치, younger sister 동생 위치
	cin >> os >> ys;
 
	cout << bfs(os, ys);

}

첫 제출에서 틀렸던 이유가 os, ys 값이 같은 경우는 이동이 필요없기 떄문에 최소 시간은 0초인데 이를 고려하지 않고 코드를 작성하여 +1, -1을 이동한 2초가 결과값으로 나오는 문제점이 있었다.

따라서 bfs 함수 상에서 os == ys 라면 바로 0을 리턴해주는 코드를 추가해주었다!
문제를 풀 때, 특별한 경우 (가능한 범위의 최대값이 input일 때, 조건 값이 같을 때 등등)를 놓치지 않고 꼼꼼하게 체크해야겠다 😓