백준 14497번 주난의 난(難)

🔒[문제 url]

https://www.acmicpc.net/problem/14497

🔑알고리즘

모든 가중치가 0 이상인 그래프에서, 특정 지점으로의 최단 경로를 구하는 문제이다.
한 걸음 나아가, 모든 가중치가 0 또는 1이기때문에 0-1 BFS를 적용할 수 있다.

• 0-1 BFS는 일반적인 BFS와 달리 deque를 이용해 가중치가 0인 지점은 push_front(), 1인 지점은 push_back()을 해준다.
  • 이로써 항상 최단경로인 지점을 우선으로 탐색하게되어 불필요한 탐색을 하지 않아도 된다.
    
    
• 문제의 요구사항에 따라, 다음 두 가지 조건으로 탐색을 진행한다.

1. 다음 지점이 0이라면, 한 번의 점프로 도달 가능하므로 현재 지점까지의 점프 횟수로 갱신한다. $visited[nx][ny] = visited[x][y]$
2. 다음 지점이 1이라면, 파동이 멈추므로 (현재 지점까지의 점프 횟수+1)로 갱신한다. $visited[nx][ny] = visited[x][y]+1$

🐾부분 코드

void BFS()
{
    int ans = 2e9;
    deque<pii> dq;
    dq.push_front(start);
    visited[start.first][start.second] = 1;

    while(!dq.empty())
    {
        int x = dq.front().first;
        int y = dq.front().second;
        dq.pop_front();

        if(x==target.first && y==target.second)
        {
            cout << visited[x][y]-1;
            return;
        }

        for(int i = 0; i < 4; i++)
        {
            int nx = x + dir[i].first;
            int ny = y + dir[i].second;
            if(nx<1 || n<nx || ny<1 || m<ny) continue;
            if(visited[nx][ny]) continue;

            if(map[nx][ny] == '0')
                visited[nx][ny] = visited[x][y],
                dq.push_front({nx,ny});
            else if(map[nx][ny] != '0')
                visited[nx][ny] = visited[x][y] + 1,
                dq.push_back({nx,ny});

        }
    }
}

<BFS 함수>
queue대신 deque를 사용해 구현한다.

🪄전체 코드

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

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int n,m;
char map[301][301];
int visited[301][301];
typedef pair<int,int> pii;
pii dir[4] = {{0,1},
              {0,-1},
              {1,0},
              {-1,0}};
pii start,target;

void INPUT()
{
    //IAMFAST
    cin >> n >> m >> start.first >> start.second >> target.first >> target.second;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%1s", &map[i][j]);
}

void BFS()
{
    int ans = 2e9;
    deque<pii> dq;
    dq.push_front(start);
    visited[start.first][start.second] = 1;

    while(!dq.empty())
    {
        int x = dq.front().first;
        int y = dq.front().second;
        dq.pop_front();

        if(x==target.first && y==target.second)
        {
            cout << visited[x][y]-1;
            return;
        }

        for(int i = 0; i < 4; i++)
        {
            int nx = x + dir[i].first;
            int ny = y + dir[i].second;
            if(nx<1 || n<nx || ny<1 || m<ny) continue;
            if(visited[nx][ny]) continue;

            if(map[nx][ny] == '0')
                visited[nx][ny] = visited[x][y],
                dq.push_front({nx,ny});
            else if(map[nx][ny] != '0')
                visited[nx][ny] = visited[x][y] + 1,
                dq.push_back({nx,ny});

        }
    }
}

void SOLVE()
{
    BFS();
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

0-1 BFS를 처음으로 깊게(?) 공부해보았다. 귀찮아서 넘기던 알고리즘이었는데, 난이도는 낮고 효율은 엄청나니 two pointer를 처음 접했을 때의 기분과 유사했다. 가중치가 0 or k(k>=1)인 상황에서 사용 가능하므로, 모두 한 번씩 공부해보길 바란다.