7562번: 나이트의 이동

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


$O(tn^2)$

BFS를 이용해 최단 거리를 구한다.

#include<cstdio>
#include<queue>
using namespace std;
queue<pair<int, int> > q;
const int fx[] = { 1,2,2,1,-1,-2,-2,-1 }, fy[] = { -2,-1,1,2,2,1,-1,-2 };
int t, n, x, y, u, v;
int main() {
    for (scanf("%d", &t); t--;) {
        int dis[300][300] = {};
        scanf("%d%d%d%d%d", &n, &x, &y, &u, &v);
        q.push({ x,y });
        dis[x][y] = 1;
        while (!q.empty()) {
            for (int i = 0; i < 8; i++) {
                int tx = q.front().first + fx[i], ty = q.front().second + fy[i];
                if (tx >= 0 && tx < n&&ty >= 0 && ty < n&&!dis[tx][ty]) {
                    dis[tx][ty] = dis[q.front().first][q.front().second] + 1;
                    q.push({ tx,ty });
                }
            }
            q.pop();
        }
        printf("%d\n", dis[u][v] - 1);
    }
    return 0;
}

2178번: 미로 탐색

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


$O(nm)$

#include<cstdio>
const int fx[] = { 0,0,1,-1 }, fy[] = { 1,-1,0,0 };
int qx[100 * 100], qy[100 * 100], h, t;
int n, m, c[100][100], r[100][100] = { 1 };
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%1d", &c[i][j]);
    qx[t] = 0; qy[t++] = 0;
    while (h^t) {
        for (int i = 0; i < 4; i++) {
            int tx = qx[h] + fx[i], ty = qy[h] + fy[i];
            if (tx<0 || ty<0 || tx >= n || ty >= m || !c[tx][ty]) continue;
            c[tx][ty] = 0;
            r[tx][ty] = r[qx[h]][qy[h]] + 1;
            qx[t] = tx; qy[t++] = ty;
        }
        h++;
    }
    printf("%d", r[n - 1][m - 1]);
    return 0;
}

1260번: DFS와 BFS

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

$O(n^2)$

DFS, BFS 구현

#include<cstdio>
const int MXN = 1e3;
int adj[MXN + 1][MXN + 1], n, m, s, ck[MXN + 1];
void dfs(int x) {
    if (ck[x]) return;
    ck[x] = 1;
    printf("%d ", x);
    for (int i = 1; i <= n; i++) if (adj[x][i]) dfs(i);
}
int q[MXN], h, t;
void bfs(int x) {
    q[t++] = x;
    ck[x] = 1;
    while (h^t) {
        printf("%d ", q[h]);
        for (int i = 1; i <= n; i++) if (adj[q[h]][i] && !ck[i]) ck[q[t++] = i] = 1;
        h++;
    }
}
int main() {
    scanf("%d %d %d", &n, &m, &s);
    for (int i = 0, x, y; i < m; i++) scanf("%d %d", &x, &y), adj[x][y] = adj[y][x] = 1;
    dfs(s);
    for (int i = 1; i <= n; i++) ck[i] = 0;
    puts("");
    bfs(s);
    return 0;
}

1697번: 숨바꼭질

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


$O(l)$

각 정수 x마다 하나의 노드를 가지고 x-1,x+1,2*x와 연결된 간선이 있다고 생각한다. BFS탐색을 통해 최소비용을 구한다.
갈 수 있는 x 위치로는 200000까지 잡으면 되는데, 이보다 큰 x를 경유해서 목적지를 가는 것보다 1칸씩 이동해서 목적지에 도달하는 것이 항상 최선이기 때문이다.

#include<cstdio>
const int MXN = 1e5;
int n, k, c[MXN * 2], q[MXN * 2], h, t;
void f(int x) {
    if (x >= 0 && x < MXN * 2 && !c[x]) c[x] = c[q[h]] + 1, q[t++] = x;
}
int main() {
    scanf("%d %d", &n, &k);
    c[n] = 1;
    q[t++] = n;
    while (h^t) {
        f(q[h] - 1); f(q[h] + 1); f(q[h] * 2);
        h++;
    }
    printf("%d", c[k] - 1);
    return 0;
}

10652번: Piggy Back

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

$O(n+m)$

1,2,n번 지점으로부터 나머지 지점까지의 최단 시간을 BFS를 통해 모두 구해 놓는다.
어떤 지점으로부터 1,2,n까지 최단 시간 합의 최솟값을 출력한다.

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int MXN = 4e4;
int b, e, p, n, m, dis[3][MXN + 1], res = 2e9;
vector<int> adj[MXN + 1];
void bfs(int h, int t) {
    queue<int> q;
    q.push(h); dis[t][h] = 1;
    while (!q.empty()) {
        for (auto it : adj[q.front()]) if (!dis[t][it]) {
            dis[t][it] = dis[t][q.front()] + 1;
            q.push(it);
        }
        q.pop();
    }
}
int main() {
    scanf("%d%d%d%d%d", &b, &e, &p, &n, &m);
    for (int i = 0, x, y; i < m; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    bfs(1, 0);
    bfs(2, 1);
    bfs(n, 2);
    for (int i = 1; i <= n; i++) res = min(res, dis[0][i] * b + dis[1][i] * e + dis[2][i] * p);
    printf("%d", res - b - e - p);
    return 0;
}

2146번: 다리 만들기

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


$O(n^2)$

섬마다 다르게 표시해놓고 섬의 각 지점을 큐에 넣고 BFS를 돌려 다른 섬간 최단 거리를 구한다.

#include<cstdio>
#include<queue>
using namespace std;
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int n, b[100][100], d[100][100], c, r = 1e9;
queue<pair<int, int> > q;
void f(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= n || !d[x][y]) return;
    d[x][y] = 0;
    b[x][y] = c;
    q.push({ x,y });
    for (int i = 0; i < 4; i++) f(x + fx[i], y + fy[i]);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) scanf("%d", d[i] + j);
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) if (d[i][j]) ++c, f(i, j);
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int tx = x + fx[i], ty = y + fy[i];
            if (tx < 0 || ty < 0 || tx >= n || ty >= n) continue;
            if (b[tx][ty]) {
                if (b[tx][ty] ^ b[x][y] && r>d[tx][ty] + d[x][y]) r = d[tx][ty] + d[x][y];
                continue;
            }
            b[tx][ty] = b[x][y];
            d[tx][ty] = d[x][y] + 1;
            q.push({ tx,ty });
        }
    }
    printf("%d", r);
    return 0;
}

3055번: 탈출

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


$O(rc)$

물->고슴도치->물->고슴도치->...
순으로 BFS를 돌려 확인한다.

#include<cstdio>
#include<queue>
using namespace std;
const int fx[] = { 1,0,-1,0 }, fy[] = { 0,1,0,-1 };
struct st { int x, y, c; };
int t, w, h, ck[50][50], tx, ty;
char s[50][51];
int main() {
    queue<st> q;
    scanf("%d%d", &h, &w);
    for (int i = 0; i < h; i++) {
        scanf("%s", s[i]);
        for (int j = 0; j<w; j++) if (s[i][j] == '*') ck[i][j] = 1, q.push({ i,j,0 });
        else if (s[i][j] == 'S') tx = i, ty = j;
    }
    ck[tx][ty] = 1; q.push({ tx,ty,1 });
    while (!q.empty()) {
        st p = q.front();
        for (int i = 0; i < 4; i++) {
            tx = p.x + fx[i]; ty = p.y + fy[i];
            if (tx < 0 || ty < 0 || tx == h || ty == w || ck[tx][ty] || s[tx][ty] == 'X') continue;
            if (s[tx][ty] == 'D') {
                if (!p.c) continue;
                printf("%d", ck[p.x][p.y]);
                return 0;
            }
            ck[tx][ty] = ck[p.x][p.y] + 1;
            q.push({ tx,ty,p.c });
        }
        q.pop();
    }
    if (q.empty()) puts("KAKTUS");
    return 0;
}

5427번: 불

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


$O(thw)$

불->상근->불->상근...
순으로 bfs를 돌려 탈출할 수 있는지 확인한다.

#include<cstdio>
#include<queue>
using namespace std;
const int fx[] = { 1,0,-1,0 }, fy[] = { 0,1,0,-1 };
struct st { int x, y, c; };
int t, w, h;
char s[1000][1001];
int main() {
    for (scanf("%d", &t); t--;) {
        int ck[1000][1001] = { 0, }, tx, ty;
        queue<st> q;
        scanf("%d%d", &w, &h);
        for (int i = 0; i < h; i++) {
            scanf("%s", s[i]);
            for (int j = 0; j<w; j++) if (s[i][j] == '*') ck[i][j] = 1, q.push({ i,j,0 });
            else if (s[i][j] == '@') tx = i, ty = j;
        }
        ck[tx][ty] = 1; q.push({ tx,ty,1 });
        while (!q.empty()) {
            st p = q.front();
            if ((!p.x || !p.y || p.x == h - 1 || p.y == w - 1) && p.c) { printf("%d\n", ck[p.x][p.y]); break; }
            for (int i = 0; i < 4; i++) {
                tx = p.x + fx[i]; ty = p.y + fy[i];
                if (tx < 0 || ty < 0 || tx == h || ty == w || ck[tx][ty] || s[tx][ty] == '#') continue;
                ck[tx][ty] = ck[p.x][p.y] + 1;
                q.push({ tx,ty,p.c });
            }
            q.pop();
        }
        if (q.empty()) puts("IMPOSSIBLE");
    }
    return 0;
}

1753번: 최단경로

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


$O(v+e)$

그냥 다익스트라 알고리즘을 돌려도 되겠지만 이 풀이는 출제자의 의도가 아닐 것이다.
간선 가중치 길이의 최댓값이 작은 것을 주목하자.
길이가 x인 간선은 그 위에 인접한 가중치가 1인 x-1개의 노드를 생성시킬 수 있다.
모든 간선에 노드를 만들고 보면 전체 그래프는 간선 가중치가 단위 길이로 같게 되며
이러한 그래프에서는 BFS를 이용해 최단 거리를 구할 수 있다.

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
const int MXV = 2e4, MXE = 3e5;
int v, t, e, k, r[MXV + MXE * 9 + 1];
vector<int> adj[MXV + MXE * 9 + 1];
queue<int> q;
int main() {
    scanf("%d%d%d", &v, &e, &k);
    t = v;
    for (int i = 0, x, y, z; i<e; i++) {
        scanf("%d%d%d", &x, &y, &z);
        if (z<2) adj[x].push_back(y);
        else {
            adj[x].push_back(++t);
            for (; --z>1;) adj[t++].push_back(t + 1);
            adj[t].push_back(y);
        }
    }
    r[k] = 1;
    q.push(k);
    while (!q.empty()) {
        for (auto it : adj[q.front()]) if (!r[it]) r[it] = r[q.front()] + 1, q.push(it);
        q.pop();
    }
    for (int i = 1; i <= v; i++) r[i] ? printf("%d\n", r[i] - 1) : puts("INF");
    return 0;
}

2516번: 원숭이

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


$O(n)$

다음을 반복한다.
1. 원숭이 i를 보았을 때 자신의 원수들이 적은 팀으로 옮긴다.(같다면 옮기지 않는다.)
2. 옮겼다면 그 팀에 속한 원숭이들에 대해 1을 적용한다.
이 알고리즘이 선형시간 안에 끝남을 증명해보자.
1번에서 옮길 원숭이가 없다면 모든 원숭이에 대해 같은 팀에 원수가 1마리 이하임을 의미하므로 프로그램을 종료한다.
1번에서 옮기는 경우가 있다면 원수 관계가 1개 이상 줄어들고 이러한 상황은 많아야 3n 번 가능하다.
증명 끝.

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int MXN = 1e5;
int n, m, t[MXN + 1], tc[2];
vector<int> adj[MXN + 1];
queue<int> q;
int main() {
    scanf("%d", &n);
    tc[0] = n;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &m);
        for (int j = 0; j < m; j++) scanf("%d", &x), adj[i].push_back(x);
        q.push(i);
        while (!q.empty()) {
            int h = q.front(), c = 0;
            for (auto it : adj[h]) c += t[h] ^ t[it] ? -1 : 1;
            if (c > 0) {
                for (auto it : adj[h]) q.push(it);
                tc[t[h]]--; t[h] = !t[h]; tc[t[h]]++;
            }
            q.pop();
        }
    }
    for (int i = 0; i<2; i++) {
        printf("%d ", tc[i]);
        for (int j = 1; j <= n; j++) if (t[j] == i) printf("%d ", j);
        puts("");
    }
    return 0;
}

2452번: 그리드 게임

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


$O(n^4)$

같은 색끼리 노드를 형성하고 인접한 노드끼리 연결해서 그래프를 만들 수 있다.
답으로 임의의 노드에 대해 해당 노드로부터 가장 멀리 떨어진 거리가 최소가 되는 거리를 출력하면 된다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
vector<int> adj[10001];
int s[100][100], c[100][100], m, n, cnt, pcnt, r = 1e9;
pair<int, int> p[40000];
void ff(int x, int y, int ss, int cc) {
    if (x < 0 || y < 0 || x >= m || y >= n || s[x][y] ^ ss || c[x][y]) return;
    c[x][y] = cc;
    for (int i = 0; i < 4; i++) ff(x + fx[i], y + fy[i], ss, cc);
}
int main() {
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) scanf("%d", &s[i][j]);
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (!c[i][j]) ff(i, j, s[i][j], ++cnt);
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) for (int k = 0; k < 4; k++) {
        int tx = i + fx[k], ty = j + fy[k];
        if (tx >= 0 && ty >= 0 && tx < m && ty < n && s[i][j] ^ s[tx][ty]) p[pcnt++] = { c[i][j],c[tx][ty] };
    }
    sort(p, p + pcnt);
    pcnt = unique(p, p + pcnt) - p;
    while (pcnt--) adj[p[pcnt].first].push_back(p[pcnt].second);
    for (int i = 1; i <= cnt; i++) {
        int q[10000], ck[10001] = { 0, }, h = 0, t = 1;
        ck[i] = 1; q[0] = i;
        while (h^t && ck[q[h]]<r) {
            for (auto it : adj[q[h]]) if (!ck[it]) {
                ck[it] = ck[q[h]] + 1;
                q[t++] = it;
            }
            h++;
        }
        r = ck[q[t - 1]];
    }
    printf("%d", r - 1);
    return 0;
}

그러나 위 소스는 대회 환경에서 시간초과로 만점을 받지 못할 것이다.
만점을 받기 위해선 적절한 컷팅이 필요한다.

1. 중간 번호 노드부터 탐색 - 보통 중간에 위치하면 최소 거리가 되기 때문
2. 탐색 노드 개수 제한 - 1번 탐색 방법에 따라 모퉁이에서 답이 나올 가능성이 거의 없음
3. bfs 탐색시 현재까지 구한 답보다 큰 거리를 탐색하면 무시하기

2206번: 벽 부수고 이동하기

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


$O(nm)$

벽을 부순적이 있는지 유무에 따라 새로운 노드를 만들어 BFS를 이용한다.

#include<cstdio>
#include<queue>
using namespace std;
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int n, m, ck[1000][1000][2] = { 1 }, c[1000][1001], r = 1e9;
struct st { int x, y, z; };
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%1d", &c[i][j]);
    queue<st> q;
    q.push({ 0,0,0 });
    while (!q.empty()) {
        st h = q.front();
        q.pop();
        if (h.x == n - 1 && h.y == m - 1) r = min(r, ck[n - 1][m - 1][h.z]);
        for (int i = 0; i < 4; i++) {
            int tx = h.x + fx[i], ty = h.y + fy[i];
            if (tx < 0 || tx >= n || ty < 0 || ty >= m || h.z&&c[tx][ty] || ck[tx][ty][h.z | c[tx][ty]]) continue;
            ck[tx][ty][h.z | c[tx][ty]] = ck[h.x][h.y][h.z] + 1;
            q.push({ tx,ty,h.z | c[tx][ty] });
        }
    }
    printf("%d", r == 1e9 ? -1 : r);
    return 0;
}

2589번: 보물섬

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


$O(n^2m^2)$

육지인 각 지점마다 BFS를 이용해 다른 지점까지의 최단 거리를 구하고 그 중 최댓값을 출력한다.

#include<cstdio>
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int n, m, qx[2500], qy[2500], r;
char str[50][51];
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", str[i]);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) if (str[i][j] == 'L') {
            int h = 0, t = 1, ck[50][50] = { 0, };
            qx[0] = i; qy[0] = j;
            ck[i][j] = 1;
            while (h^t) {
                for (int k = 0; k < 4; k++) {
                    int tx = qx[h] + fx[k], ty = qy[h] + fy[k];
                    if (tx < 0 || ty < 0 || tx >= n || ty >= m || str[tx][ty] == 'W' || ck[tx][ty]) continue;
                    ck[tx][ty] = ck[qx[h]][qy[h]] + 1;
                    if (ck[tx][ty] - 1>r) r = ck[tx][ty] - 1;
                    qx[t] = tx; qy[t++] = ty;
                }
                h++;
            }
        }
    }
    printf("%d", r);
    return 0;
}

2636번: 치즈

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


$O(n^3)$

#include<cstdio>
#include<string.h>
const int fx[] = { 0,0,1,-1 }, fy[] = { 1,-1,0,0 };
int n, m, c[102][102], ck[102][102], s, t, r;
void f(int x, int y) {
    if (x<0 || y<0 || x>n + 1 || y>m + 1 || ck[x][y])return;
    ck[x][y] = 1;
    if (c[x][y]) { c[x][y] = 0; s--; r++; return; }
    for (int i = 0; i < 4; i++) f(x + fx[i], y + fy[i]);
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) scanf("%d", c[i] + j), s += c[i][j];
    for (; s; t++) memset(ck, 0, sizeof(ck)), r = 0, f(0, 0);
    printf("%d\n%d", t, r);
    return 0;
}

$O(n^2)$

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int MXN = 100, fx[] = { 1,-1,0,0 }, fy[] = { 0,0,1,-1 };
int n, m, c[MXN + 2][MXN + 2], ck[MXN + 2][MXN + 2], t, r;
queue<pair<int, int> > q;
void f(int x, int y, int z) {
    if (c[x][y]) if (z > t) t = z, r = 1; else if (z == t)r++;
    ck[x][y] = z;
    for (int i = 0; i < 4; i++) {
        int tx = x + fx[i], ty = y + fy[i];
        if (tx<0 || ty<0 || tx>n + 1 || ty>m + 1 || ck[tx][ty]) continue;
        c[tx][ty] ? ck[tx][ty] = z + 1, q.push({ tx,ty }) : f(tx, ty, z);
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &c[i][j]);
    f(0, 0, 1);
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        f(x, y, ck[x][y]);
        q.pop();
    }
    printf("%d\n%d", t - 1, r);
    return 0;
}

2593번: 엘리베이터

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


$O(n+m)$

엘리베이터로 갈 수 있는 모든 층들의 노드를 만들고 각 엘리베이터마다 서는 층들을 하나의 더미 노드를 더 만들어 이것과 층들을 연결해놓는다. 이제 bfs 탐색을 하면 최단 비용을 구할 수 있다. 더미 노드를 이용했으니 실제로 드는 비용은 절반일 것이다.
아래 소스와 같이 문제에서 주어진 시작점이 아닌 끝점부터 탐색을 시작한다면 재귀호출 대신 간단한 for문으로 경로를 출력할 수 있다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 1e5 + 100;
int n, m, a, b, go[MXN + 1], c[MXN + 1], q[MXN], h, t;
vector<int> adj[MXN + 1];
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1, x, y; i <= m; i++) {
        scanf("%d %d", &x, &y);
        for (int j = x; j <= n; j += y) adj[n + i].push_back(j), adj[j].push_back(n + i);
    }
    scanf("%d %d", &a, &b);
    for (int i = 1; i <= n + m; i++) c[i] = -2;
    c[b] = 0;
    q[t++] = b;
    while (h != t) {
        for (auto it : adj[q[h]]) if (c[it] == -2) {
            q[t++] = it;
            c[it] = c[q[h]] + 1;
            go[it] = q[h];
        }
        h++;
    }
    printf("%d\n", c[a] / 2);
    for (int i = go[a]; i; i = go[go[i]]) printf("%d\n", i - n);
    return 0;
}

2481번: 해밍 경로

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


$O(nk\lg n+nm)$

각 수에 대해 한 자리씩 바꿔보면서 그래프를 형성한 다음, BFS를 돌리자. 처음 방문할 때까지 드는 비용이 최소 비용이다.

#include<stdio.h>
#include<vector>
#include<map>
using namespace std;
const int MAX_N = 1e5;
int n, m, k, q[MAX_N], h, t, fr[MAX_N + 1], ck[MAX_N + 1];
map<int, int> mp;
vector<int> adj[MAX_N + 1];
void f(int x) {
    if (x != 1) f(fr[x]);
    printf("%d ", x);
}
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        int t = 0;
        for (int j = 0, x; j < k; j++) scanf("%1d", &x), t += (1 << j)*x;
        mp[t] = i;
    }
    for (auto it : mp) {
        for (int i = 0; i < k; i++) {
            auto t = mp.find(it.first ^ (1 << i));
            if (t != mp.end()) adj[it.second].push_back(t->second);
        }
    }
    q[t++] = ck[1] = fr[1] = 1;
    while (h ^ t) {
        for (auto it : adj[q[h]]) {
            if (ck[it]) continue;
            q[t++] = it;
            fr[it] = q[h];
            ck[it] = 1;
        }
        h++;
    }
    scanf("%d", &m);
    for (int i = 0, x; i < m; i++) {
        scanf("%d", &x);
        fr[x] ? f(x), puts("") : puts("-1");
    }
    return 0;
}

5214번: 환승

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


$O(n+mk)$

bfs 구현문제이다.
bfs 탐색에서 모든 간선 비용이 단위 값으로 이루어져 있다면 처음 방문하기까지의 비용이 최소 비용임을 이용하자.

#include<stdio.h>
#include<vector>
using namespace std;
const int MAX_S = 1e5 + 1e3;
int n, k, m, ck[MAX_S + 1], q[MAX_S], t;
vector<int> adj[MAX_S + 1];
int main() {
    scanf("%d %d %d", &n, &k, &m);
    for (int i = n + 1; i <= n + m; i++)
        for (int j = 0, c; j < k; j++)
            scanf("%d", &c), adj[c].push_back(i), adj[i].push_back(c);
    q[t++] = ck[1] = 1;
    for (int h = 0; h < t; h++)
        for (auto it : adj[q[h]])
            if (!ck[it]) ck[q[t++] = it] = ck[q[h]] + 1;
    printf("%d", ck[n] ? ck[n] / 2 + 1 : -1);
    return 0;
}