1차원 BFS, DP

https://school.programmers.co.kr/learn/courses/30/lessons/148653

프로그래머스

이 문제를 보고 어떻게 풀어야 좋을지를 생각하던 도중, 관련된 다른 문제들이 생각나서 정리를 해보게 되었다.

1. BFS 

• bfs문제는 대부분 2차원 격차에서 길을 찾는 문제를 풀 때 많이 사용했을 것이다.
• 그러나 다음과 같은 문제에서도 사용할 수 있다. (백준 1697 숨바꼭질: https://www.acmicpc.net/problem/1697)

백준 1697

 

해당 문제에 대해 해설을 해보자면,

• board라는 배열은 현재 자리(배열에 index에 해당하는) 에 올 때 까지 필요한 시간을 뜻한다.
• queue는 bfs를 풀 때 사용하는 것 처럼 현재 위치를 가지는 역할을 한다.
• 먼저 board 배열을 -1로 초기화한 후 수빈이의 위치의 값을 0으로 한다.
• 이후 동생의 위치에 오기 전까지 반복해서 bfs를 진행하면 된다.
  • 동생이 있는 위치를 처음으로 도달한 순간이 가장 빠른 시간이기 때문에, while문의 종료조건이 if(board[k] == -1) 이다.
  • 이때 바운더리 체크를 할 때, if(nxt < 0 || nxt > 100'000) 인 이유는
    • 0보다 작은 값으로 가는 행위는 당연하게도 가장 빠른 경로가 아니고
    • 100'000 보다 큰 값으로 갈 수 도 있지만, *2를 통해 100'000을 넘어서면 -1을 통해서만 k위치까지 돌아와야 하기 때문에 손해이기 때문이다.
• 추가적으로 range based for문을 통해 현재 위치에서 -1, +1, *2 의 위치를 쉽게 구할 수 있었다.
• 정답 코드

#include <iostream>
#include <queue>
using namespace std;

int n, k;
int board[100'002];
queue<int> q;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
    
	//초기화
	fill(board, board + 100'002, -1);
	
	// 수빈이의 위치
	board[n] = 0;
	q.push(n);

	while (board[k] == -1)
	{
		int cur = q.front();
		q.pop();

		for (int nxt : {cur - 1, cur + 1, 2 * cur})
		{
			if (nxt < 0 || nxt > 100'000)
				continue;
			if (board[nxt] != -1)
				continue;
			board[nxt] = board[cur] + 1;
			q.push(nxt);
		}
	}	

	cout << board[k];
}

 

2. DP

• 처음에 이 문제를 보고, 위에서 했던 bfs 풀이가 떠올랐지만 해당 문제는 dp로 푸는 것이 더욱 간단한 문제이다.
• 백준 1463 https://www.acmicpc.net/problem/1463

백준 1463

먼저 bfs로 해당 문제에 대한 풀이를 해보면, 

• 푸는 방식은 위의 코드와 동일하지만, 
• 문제에서는 주어진 수를 나누고 빼서 1을 만드는 것이지만, 우리는 1에서 곱하고 더해서 주어진 수를 만드는 방향으로 바꿔서 풀면 쉽게 해결할 수 있다.

#include <iostream>
#include <queue>
using namespace std;

int x; 
int board[1'000'002];
queue<int> q;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> x;
	fill(board, board + 1'000'002, -1);

	board[1] = 0;
	q.push(1);

	while (board[x] == -1)
	{
		int cur = q.front();
		q.pop();

		for (int nxt : {cur * 3, cur * 2, cur + 1})
		{
			if (nxt <= 0 || nxt > 1'000'000)
				continue;
			if (board[nxt] != -1)
				continue;
			board[nxt] = board[cur] + 1;
			q.push(nxt);
		}
	}

	cout << board[x];
}

 

그렇다면, 이제 DP로 이 문제를 다시 풀어보면

• DP는 항상 테이블 정의, 초기값 설정, 점화식 세우기 세가지만 잘 하면 된다.
• 예전에 DP 문제를 풀다가 생각을 정리한 내용. https://velog.io/@gb_leem/Coding-Test-Dynamic-Programming
• 이 문제에서는
  • 테이블: 문제의 목적을 보고 정하기
    • 이 문제의 목적이 x를 1로 만드는데 필요한 "최소 횟수" 이므로 
    • 테이블은 1차원 배열로 선언하고, i를 1로 만드는데 필요한 최소 횟수로 두면 된다.
  • 점화식: 우리가 할 수 있는 연산과 특정 상황을 가정해보고 작성하기
    • 우리가 할 수 있는 연산은 1을 빼기, 3으로 나누기 2로 나누기 이므로
    • 이 세가지 상황 중에서 가장 작은 횟수를 구하도록 점화식을 세우면 된다.
    • dp[x] = min(dp[x/2] + 1, dp[x/3] + 1, d[x-1] + 1); 
    • 이때 2와 3으로 나눠떨어지는 경우만 나눌 수 있으므로, 그것에 대한 체크만 추가로 해주자
  • 초기값: 우리가 대입해보면서 바로 얻을 수 있는 값이며, 점화식의 범위에 들어오는 값
    • 이 문제에서 가장 작은 값은 1일 것이고, 1을 1로 만드는데 필요한 횟수는 0이다.
    • 또한 우리가 점화식에서 x-1 연산을 해야하므로, 점화식을 x가 2일때 시작하면, 범위를 벗어나는 일도 없어지므로 초기값으로 설정해도 좋을 것이다. (dp[2 -1] -> dp[1] 이므로 )
• 정답 코드

#include <iostream>
using namespace std;

int x;
int dp[1'000'002]; //i를 1로 만들 때 필요한 연산의 수

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> x;
	dp[1] = 0;

	for (int i = 2; i <= x; ++i)
	{
		dp[i] = dp[i - 1] + 1; //어느 상황에서나 적용해야 하므로,

		if (i % 2 == 0)
			dp[i] = min(dp[i], dp[i / 2] + 1);
		if (i % 3 == 0)
			dp[i] = min(dp[i], dp[i / 3] + 1);
	}
	cout << dp[x];
}

3. 이제 맨 처음에 언급한 문제를 풀어보자

이 문제는 프로그래머스 level2의 마법의 엘리베이터 문제이다.

https://school.programmers.co.kr/learn/courses/30/lessons/148653

• 생각해야 할 포인트는 예시의 경우 처럼 16이 input인 경우이다.
  • 16 -> 10 -> 0 : 우리가 단순히 생각하는 경로일 것이다. 그러나 이 경우 7개의 돌이 필요하다.
  • 16 -> 20 -> 0: 이 경우 올라갔다가 내려오는 경로가 되고, 6개의 돌이 필요하여 위의 경우보다 적은 수가 필요하게 된다.
• 그래서 위로 갈수도, 아래로 갈수도 있다고 생각하여, 1차원 BFS를 생각하게 된 것 같다.
• 추가적으로 생각할 점
  • 갈 수 있는 곳이 항상 위와 아래가 있으므로, 두 경우를 각각의 상황마다 계산해주어야 하는 점이다.
  • 또한 0이 된 경우는 q에 집어넣지 않아서 while문을 탈출할 수 있도록 해주었다.

#include <string>
#include <vector>
#include <queue>
using namespace std;

int board[100'000'002];
queue<int> q;

int solution(int storey)
{
    //초기화
    fill(board, board + 100'000'002, -1);
    
    //시작값 대입
    board[storey] = 0;
    q.push(storey);

    while (!q.empty())
    {
        int cur = q.front();
        q.pop();

        int mod = cur % 10; //1의 자릿수 구하기 

        int small = -mod;   //내려가기
        int big = 10 - mod; //올라가기

        for (int nxt : {small, big})
        {
            //맨 처음으로 나머지 처리를 한 뒤에는 나머지가 계속 0이되기 때문에
            //10으로 나눈 값을 넣어주는 식으로 처리하였고,
            //이전의 값과 비교가 필요해서 realNxt를 구해주는 방식으로 구현하였다.
            int realNxt = cur + nxt; 
            if (realNxt == cur * 10)
                continue;
            realNxt /= 10;

            //바운더리 체크
            if (realNxt < 0 || realNxt > 100'000'000)
                continue;

            //돌의 갯수 계산
            if (board[realNxt] != -1)
                board[realNxt] = min(board[cur] + abs(nxt), board[realNxt]);
            else
                board[realNxt] = board[cur] + abs(nxt);

            //도착한 경우
            if (realNxt != 0)
                q.push(realNxt);
        }
    }

    return board[0];
}

• 답은 맞았지만, 코드가 깔끔하지는 않다고 생각이 되어 다른 사람의 풀이를 찾아보았다. 가장 인상깊은 코드를 보여주자면 아래의 코드이다
• bfs를 쓰지 않아도 해결할 수 있는 문제였고, 올라가는 경우 if 조건문이 키포인트인 코드이다. 또한 storey를 ++ 해줌으로서 올림을 구현한 부분도 배울점이 있는 코드였다.

int solution(int storey) 
{
    int answer = 0;
    int temp;

    while (storey > 0) 
    {
        temp = storey % 10;
        storey = storey / 10;
        //올라가는 경우
        if (temp > 5 || (temp == 5 && storey % 10 >= 5)) 
        {
            answer += 10 - temp;
            storey++;
        }
        //내려가는 경우
        else 
        {
            answer += temp;
        }        
    }

    return answer;
}

 

4. DP? BFS?

• 그렇다면, 언제 DP를 쓰고 BFS를 쓰는 것이 좋을까...
• 명확히 언제 무엇을 쓰고 이런식으로 정하는 것은 어려워 보인다.
• 살짝 힌트로 생각할 만한 것은 너무 큰 데이터 값이 주어진다면, bfs 는 아닐 것이라고 생각하는 것이 좋을 것 같다.
• 왜냐면 대부분의 BFS DFS는 2차원 배열이므로 행과 열이 10^4를 넘어가면, 배열을 선언조차 할 수 없어진다.