백준 1981 배열에서 이동

이진탐색 좀 여려워 보이는 문제를 잡았다.

단순히 배열의 값에서 탐색해서 값을 찾는것이 아닌, 뭔가 2D 맵을 탐색하는 문제이다.

2차원 배열의 0,0에서 우하단 자리인 n, n까지 이동할때, 전체 경로의 최대값과 최소값 차이의 최소를 찾는 문제이다.

 

문제 풀이는 어떻게 되냐하면, 경로상 최소-최대 값 차이가 정해졌을때, 이 경로로 갈 수 있는지 탐색하는 bfs 함수를 만든다.

이 함수를 이용해 diff값을 이진탐색을 하며 찾는다. 처음 diff값은 (start=0, end=(맵 max - 맵 min))이고, mid값은 start와 end값의 중간이다. 만약 mid값으로 탐색이 가능하다면, 우리는 더 낮은 diff값으로 탐색을 해야한다. 여기서 end = mid - 1로 갱신하여 또 탐색을 한다.

-> 흔히 보던 이진탐색이다.

 

주어진 diff 값으로 탐색이 가능한지 찾는 방법은, 단순히 맵에서 갈 수 있는부분을 제한하는 방식으로 작성했다. 맵 최소값부터 최대값까지 순회(i)하면서, 각 맵의 값이 i ~ i+diff 인지 확인해, 그 범위에 들어오는 위치만 방문 가능하도록 visited[][] 배열을 초기화하였다.

그 visited 배열을 사용해 탐색만 하면 된다. 중간에 마지막 위치까지 가게 되면 탐색이 가능한것이므로 무조건 바로 return 한다.

모든 루프가 돌고나서 리턴이 되지 않았다면 탐색이 불가능하므로 false를 리턴한다.

---

#include <iostream>
#include <queue>
#include <cstring>

#define MAX 100

int n, max_val, min_val;
int g_map[MAX][MAX];
bool g_visit[MAX][MAX];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

bool bfs(int diff)
{
    std::queue<int> q;

    for (int i = min_val ; i <= max_val; i++)
    {
        memset(g_visit, true, sizeof(g_visit));

        for (int r = 0; r < n; r++)
        {
            for (int c = 0; c < n; c++)
            {
                if (i <= g_map[r][c] && g_map[r][c] <= i + diff)
                    g_visit[r][c] = false; // diff 차이로 갈 수 있는곳만 false로 만들어두기
            }
        }
        q.push(0);

        while (!q.empty())
        {
            int r = q.front() / n;
            int c = q.front() % n;
            q.pop();

            if (g_visit[r][c])
                continue; // 이미 방문한곳 패스
            g_visit[r][c] = true;

            if (r == n-1 && c == n-1) return true; // 끝까지 왔음 -> 탐색종료

            for (int dir = 0 ; dir < 4 ; dir++)
            {
                int nr = r + dy[dir];
                int nc = c + dx[dir];

                if (nr >= 0 && nc >= 0 && nr < n && nc < n)
                    q.push(nr * n + nc);
            }
        }
        
    }
    return false;
}

int main()
{
    max_val = -1;
    min_val = 500;

    std::cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            std::cin >> g_map[i][j];
            max_val = std::max(g_map[i][j], max_val);
            min_val = std::min(g_map[i][j], min_val);
        }
    }

    // 이진탐색
    int start = 0;
    int end = max_val - min_val;
    int mid;

    while (start <= end)
    {
        mid = (start + end) / 2;
        if (bfs(mid) == true) 
            end = mid - 1;
        else
            start = mid + 1;
    }
    std::cout << end + 1;
}

 

이진탐색의 응용이 되면 조금 문제가 다채로워지는것 같다. 이렇게 이진탐색을 응용할줄은 몰랐다. 다른 문제들도 풀어봐야겠다...

 

오늘도 평온한 하루가 되길. 슨민.