[1261] 알고스팟

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

1261번: 알고스팟

<문제>

꽤 다양한 풀이가 있을 수 있는 문제이다.

현재 위치를 정점으로 생각하면, 상하좌우로 연결된 그래프라고 생각할 수 있다.

다음 정점이 0인경우, 가중치가 0인 간선이 존재하는 셈이고

다음 정점이 1인경우, 가중치가 1인 간선이 존재하는 셈이다.

문제를 이렇게 변형한다면

1만개의 정점, 0 혹은 1의 가중치를 갖는 양방향 그래프에서 [1,1]->[M,N] 다익스트라로 해결이 가능하다.

 

이를 조금더 개선한 방법중 하나가, 가중치가 0 혹은 1일때에 사용하는 특수한 형태의 bfs도 존재하는데,

0-1bfs 테크닉을 사용하지 않아도 이 문제는 입력이 작은 관계로 일반적인 bfs로도 해결이 가능한 것으로 보인다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX;
int n, m, dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0}, a[101][101];
queue<pair<int, int>> q;
int main(void) {
    int i, j;
    cin >> m >> n;
    string temp;
    for (i = 0; i < n; i++) {
        cin >> temp;
        for (j = 0; j < m; j++) {
            a[i][j] = temp[j] - '0';
        }
    }
    vector<vector<int>> dist(100, vector<int>(100, INF));
    q.push({0, 0});
    dist[0][0] = 0;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        for (i = 0; i < 4; i++) {
            int y = cur.first + dy[i];
            int x = cur.second + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m) continue;
            if (a[y][x] == 0) {
                if (dist[y][x] > dist[cur.first][cur.second]) {
                    dist[y][x] = dist[cur.first][cur.second];
                    q.push({y, x});
                }
            } else if (a[y][x] == 1) {
                if (dist[y][x] > dist[cur.first][cur.second] + 1) {
                    dist[y][x] = dist[cur.first][cur.second] + 1;
                    q.push({y, x});
                }
            }
        }
    }
    cout << dist[n - 1][m - 1];
 
    return 0;
}

n : 행
m : 열