[중급 알고리즘] BFS

💚 16928 뱀과 사다리 게임

- 100개의 칸으로 나누어져 있는 게임이 있다. 1에서 100으로 가야 한다.

- 주사위를 굴려 나온 수만큼 이동할 수 있으며, 도착한 카이 사다리인 경우에는 사다리를 타고 더 큰 번호의 칸으로, 뱀인 경우에는 더 작은 번호의 칸으로 이동한다.

- 주사위에 나온 수를 정할 수 있을 때, 최소 몇 번 굴려야 하는지 구하는 문제

 

- 게임에서 뱀과 사다리의 구분은 중요하지만 구현에서는 별로 중요하지 않다.

- x ➡️ y로 간다는 점만 중요하다.

- 새로운 배열 next[x]를 만들어서, x에 도착한 이후에 가야할 곳을 모두 기록

- 뱀이나 사다리인 경우에는

next[x] = y

- 일반 칸인 경우에는

next[x] = x

#include <iostream>
#include <algorithm>
#include <queue>
#define next _next
using namespace std;
// 1로부터의 거리 저장
int dist[101];
// next[i]: i에 도착한 이후에 가야하는 곳 저장
int next[101];

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1;i <= 100;i++) {
        next[i] = i;
        dist[i] = -1;
    }

    while(n--) {
        int x, y;
        cin >> x >> y;
        next[x] = y;
    }

    while(m--) {
        int x, y;
        cin >> x >> y;
        next[x] = y;
    }

    dist[1] = 0;
    queue<int> q;
    q.push(1);

    while(!q.empty()) {
        int x = q.front();
        q.pop();
        // 주사위 돌리기
        for(int i = 1;i <= 6;i++) {
            int y = x + i;
            if(y > 100) continue;
            y = next[y];
            if(dist[y] == -1) {
                dist[y] = dist[x] + 1;
                q.push(y);
            }
        }
    }

    cout <<dist[100] << '\n';
    return 0;
}

💚 169489 데스 나이트

- 데스나이트는 (r, c)에서 (r - 2, c - 1), (r - 2, c + 1), (r, c - 2), (r, c + 2),  (r + 2, c - 1), (r + 2, c + 1)로 이동할 수 있는 말이다.

- 크기가 N * N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어졌을 때, (r1, c1)에서 (r2, c2)로 가는 최소 이동 횟수를 구하는 문제

- 5 <= N <= 200

 

💚 9019 DSLR

- 이 문제는 최소값을 구해야하는 건 맞지만

- 어떠한 과정을 거쳐야하는지를 구해야 한다.

- 배열을 하나 더 이용해서 어떤 과정을 거쳤는지를 저장해야 한다.

- how[i] = i를 어떻게 만들었는지

 -대신 모두 기록하면 너무 많은 공간을 차지하기 때문에 안됨

재귀로도 푸는 방법이 있다.

#include <iostream>
void print(int A, int B){
    if(A == B) return;
    print(A, from[B]);
    cout << how[B];
}

이전의 내 BFS 풀이

결과물과 결과물을 만든 명령어를 함께 Queue에 입력한다.

그리고 방문된 적 없는 숫자만 확장해나간다는 특징이 있다.

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

using namespace std;
const int MAX = 10000;
int visited[MAX];
string bfs(int a, int b);

int main(void){
    int t;
    int a, b;
    cin >> t;
    while(t--){
        memset(visited,false,sizeof(visited));
        cin >> a >> b;
        cout << bfs(a,b) << endl;
    }
}
string bfs(int a, int b){
    int next;
    int num;
    string command;

    queue<pair<int, string>> q;
    
    q.push(make_pair(a, ""));

    visited[a] = true;
    
    while(!q.empty()){
        num = q.front().first;
        command = q.front().second;
        
        q.pop();
        
        if(b == num)
            break;
        //D
        next = (num * 2) % MAX;
        if(!visited[next]){
            visited[next] = true;
            q.push(make_pair(next,command+ "D"));
        }
        
        //S
        next = (num - 1) < 0? 9999 : num -1;
        if(!visited[next]){
            visited[next] = true;
            q.push(make_pair(next,command+ "S"));
        }
        
        //L
        next = (num % 1000) * 10  + num / 1000;
        if(!visited[next]){
            visited[next] = true;
            q.push(make_pair(next,command+ "L"));
        }
        
        //R
        next = (num % 10) * 1000 + (num / 10);
        if(!visited[next]){
            visited[next] = true;
            q.push(make_pair(next,command+ "R"));
        }
    }
    return command;
}

 

💚 14502 연구소

문제를 아래와 같이 크게 2개로 나눌 수 있다.

벽을 3개 세워서(재귀로 조합 생성) / 바이러스가 퍼질 수 없는 곳의 크기(DFS or BFS)를 구하기

 

이 문제는 최소가 특징인 점이 아니기에 하나의 정점에서 모든 정점을 방문하는 DFS로도 풀 수 있다.

(DFS/BFS의 목적: 한 정점에서 시작해 연결된 모든 정점을 방문)

 

벽을 3개 세우는 경우의 수: (NM)^3

벽을 세운 다음 안전 영역의 크기를 구하는 방법: BFS / DFS로 O(NM)

총 O((NM)^4)가 나오는데, N,M <= 8이기 때문에 시간 안에 해결할 수 있다.

BFS

#include <iostream>
#include <queue>

using namespace std;
int n, m;
int a[10][10];
int b[10][10];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
int bfs() {
    queue<pair<int, int>> q;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            b[i][j] = a[i][j];
            if(b[i][j] == 2) {
                q.push({i, j});
            }
        }
    }

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

        q.pop();
        for(int k = 0;k < 4;k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(inside(nx, ny) && b[nx][ny] == 0) {
                b[nx][ny] = 2;
                q.push({nx, ny});
            }
        }
    }
    int cnt = 0;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            if(b[i][j] == 0) {
                cnt++;
            }
        }
    }
    return cnt;
}
int main() {
    cin >> n >> m;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++) {
            cin >> a[i][j];
        }
    }

    int ans = 0;
    for(int x1 = 0;x1 < n;x1++) {
        for(int y1 = 0;y1 < m;y1++) {
            if(a[x1][y1] != 0) continue;
            for(int x2 = 0;x2 < n;x2++) {
                for(int y2 = 0;y2 < m;y2++){
                    if(a[x2][y2] != 0) continue;
                    for(int x3 = 0;x3 < n;x3++) {
                        for(int y3 = 0;y3 < m;y3++) {
                            if(a[x3][y3] != 0) continue;
                            if(x1 == x2 && y1 == y2) continue;
                            if(x2 == x3 && y2 == y3) continue;
                            if(x1 == x3 && y1 == y3) continue;
                            a[x1][y1] = 1;
                            a[x2][y2] = 1;
                            a[x3][y3] = 1;
                            int cur = bfs();
                            if(cur > ans) ans = cur;
                            a[x1][y1] = 0;
                            a[x2][y2] = 0;
                            a[x3][y3] = 0;
                        }
                    }
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

DFS

#include <iostream>
#include <queue>

using namespace std;
int n, m;
int a[10][10];
int b[10][10];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
void dfs(int x, int y) {
    for(int k = 0;k < 4;k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if(inside(nx, ny) && b[nx][ny] == 0) {
            b[nx][ny] = 1;
            dfs(nx, ny);
        }
    }
}
int dfs() {
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            b[i][j] = a[i][j];
        }
    }

    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            if(b[i][j] == 2) {
                dfs(i, j);
            }
        }
    }

    int cnt = 0;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            if(b[i][j] == 0) {
                cnt++;
            }
        }
    }

    return cnt;
}

int main() {
    cin >> n >> m;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++) {
            cin >> a[i][j];
        }
    }

    int ans = 0;
    for(int x1 = 0;x1 < n;x1++) {
        for(int y1 = 0;y1 < m;y1++) {
            if(a[x1][y1] != 0) continue;
            for(int x2 = 0;x2 < n;x2++) {
                for(int y2 = 0;y2 < m;y2++){
                    if(a[x2][y2] != 0) continue;
                    for(int x3 = 0;x3 < n;x3++) {
                        for(int y3 = 0;y3 < m;y3++) {
                            if(a[x3][y3] != 0) continue;
                            if(x1 == x2 && y1 == y2) continue;
                            if(x2 == x3 && y2 == y3) continue;
                            if(x1 == x3 && y1 == y3) continue;
                            a[x1][y1] = 1;
                            a[x2][y2] = 1;
                            a[x3][y3] = 1;
                            int cur = dfs();
                            if(cur > ans) ans = cur;
                            a[x1][y1] = 0;
                            a[x2][y2] = 0;
                            a[x3][y3] = 0;
                        }
                    }
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

💚12886 돌 그룹

- 최소의 값을 구하는 것이 아니므로 DFS/BFS 모두 가능

- 전체 정점의 개수: A + B + C개 / A + B개(어차피 C = N - A - B이기 때문)

- 전체를 탐색하기에는 너무 경우의 수가 커진다.

#include <iostream>
#include <queue>

using namespace std;
bool check[1501][1501];
int sum;
// 가능한 구성인지
void go(int x, int y) {
    // (x, y, sum - y - x) 조합은 이미 탐색됨
    if(check[x][y]) return;

    check[x][y] = true;
    // 비교용
    int a[3] = {x, y, sum - x - y};
    for(int i = 0;i < 3;i++) {
        for(int j = 0;j < 3;j++) {
            // a[j]에서 a[i]로 전달
            if(a[i] < a[j]) {
                int b[3] = {x, y, sum - x - y};
                b[i] += a[i];
                b[j] -= a[i];
                go(b[0], b[1]);
            }
        }
    }

}

int main() {
    int x, y, z;
    cin >> x >> y >> z;
    sum = x + y + z;
    // 불가능한 조건
    if(sum % 3 != 0) {
        cout << 0 << '\n';
        return 0;
    }

    go(x, y);

    if(check[sum / 3][sum / 3]) {
        cout << 1 << '\n';
    } else {
        cout << 0 << '\n';
    }
    return 0;
}

💚2206 벽 부수고 이동하기

- N * M의 행렬로 나타내는 지도에서 (1, 1)에서 (N, M)으로 최단 거리로 이동하는 문제

- 0은 빈칸, 1은 벽

- 벽은 한 번 부수고 지나갈 수 있다는 점에서 여기에서 정점은 단순히 r, c 뿐만 아니라 k라는 벽을 부순 횟수를 따로 저장해야 한다.

- 이전에 구슬 던지기 문제와 유사하게 Queue에 여러개의 정보를 저장하기 위해 tuple을 사용한다.

#include <iostream>
#include <queue>
// 순서대로 정리
#include <tuple>

using namespace std;
// map
int a[1000][1000];
// r, c, k(벽 부순 유무)
int d[1000][1000][2];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int n, m;
bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
int main() {

    scanf("%d %d", &n, &m);
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            scanf("%1d", &a[i][j]);
        }
    }

    queue<tuple<int, int, int>> q;
    d[0][0][0] = 1;
    q.push({0,0,0});
    while(!q.empty()) {
        int x, y, z;
        tie(x, y, z) = q.front();
        q.pop();
        for(int k = 0;k < 4;k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if(!inside(nx, ny)) continue;
            // 빈칸이고 방문한 적도 없는 칸
            if(a[nx][ny] == 0 && d[nx][ny][z] == 0) {
                // 이동 기록
                d[nx][ny][z] = d[x][y][z] + 1;
                q.push(make_tuple(nx, ny, z));
            }

            // 아직 벽을 부순 적이 없고 빈칸이 아니고 방문한 적도 없는 칸
            if(z == 0 && a[nx][ny] == 1 && d[nx][ny][z + 1] == 0) {
                d[nx][ny][z + 1] = d[x][y][z] + 1;
                q.push(make_tuple(nx, ny, z + 1));
            }
        }
    }

    // 벽을 부수고도, 부수지 않고도 통과
    if(d[n - 1][m - 1][0] != 0 && d[n - 1][m - 1][1] != 0) {
       cout << min(d[n - 1][m - 1][0], d[n - 1][m - 1][1]);
    }
    else if(d[n - 1][m - 1][0] != 0) {
        cout << d[n - 1][m - 1][0];
    }
    else if(d[n - 1][m - 1][1] != 0) {
        cout << d[n - 1][m - 1][1];
    } else {
        cout << -1;
    }
    return 0;


}

💚16946 벽 부수고 이동하기4

앞 문제보다 살짝 더 복잡하다.

문제가 말한 그대로 지금 위치에서 벽을 부수고 매번 이동할 수 있는 칸의 수를 세면 지나치게 비효율적이다.

N, M <= 1000이므로 (1000 * 1000)^2으로 1조 정도의 경우의수를 탐색해야 한다.

 

이동할 수 있는 빈칸을 모두 그룹 짓는다.

그리고 근처의 빈칸 그룹을 탐색한 후 그룹의 크기+ 1(현재 벽인 칸)이 매번 이동할 수 있는 칸의 수가 나온다.

이렇게 진행하면 빈칸 그룹을 찾는 데 O(NM) + 근처의 그룹을 찾는 데 O(NM) = O(NM)이라는 시간 복잡도가 나온다.

 

#include <iostream>
#include <queue>
#include <set>
#include <tuple>
using namespace std;
int n, m;
// 벽, 빈 칸 표시
int a[1000][1000];
// 방문 여부
int check[1000][1000];
// 소속 그룹
int group[1000][1000];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
vector<int> group_size;
bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
void bfs(int sx, int sy) {
    queue<pair<int, int>> q;
    int g = group_size.size();

    // 초기 세팅
    int cnt = 1;
    q.push({sx, sy});
    check[sx][sy] = true;
    // 새로운 그룹의 시작
    group[sx][sy] = g;
    while(!q.empty()) {
        int x, y;
        tie(x, y) = q.front();
        q.pop();
        for(int k = 0;k < 4;k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(!inside(nx, ny)) continue;
            if(a[nx][ny] == 0 && check[nx][ny] == false) {
                check[nx][ny] = true;
                q.push({nx, ny});
                group[nx][ny] = g;
                cnt++;
            }
        }
    }
    group_size.push_back(cnt);
}
int main() {
    cin >> n >> m;
    for(int i = 0;i < n;i++) {
        string s;
        cin >> s;
        for(int j = 0;j < m;j++) {
            a[i][j] = s[j] - '0';
            check[i][j] = false;
            group[i][j] = -1;
        }
    }

    // 그룹 생성
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            if(a[i][j] == 0 && check[i][j] == false) {
                bfs(i, j);
            }
        }
    }

    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            if(a[i][j] == 0)
                cout << 0;
            else {
                set<int> near;
                for(int k = 0;k < 4;k++) {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if(!inside(x, y)) continue;
                    // 주변에 빈 칸이 있으면 해당 그룹을 set에 추가
                    if(a[x][y] == 0) near.insert(group[x][y]);
                }

                int ans = 1;
                for(int g : near){
                    ans += group_size[g];
                }
                cout << ans % 10;
            }
        }
        cout << '\n';
    }
    return 0;
}

💚16942 벽 부수고 이동하기2

- N *M의 행렬로 나타내는 지도에서 (1, 1)에서 (N, M)으로 최단 거리로 이동하는 문제

- 0은 빈칸, 1은 벽

- 단 벽은 K번까지 부수고 지나갈 수 있다.

 

💚16933 벽 부수고 이동하기3

- N *M의 행렬로 나타내는 지도에서 (1, 1)에서 (N, M)으로 최단 거리로 이동하는 문제

- 0은 빈칸, 1은 벽

- 이동할 때마다 낮과 밤이 바뀐다

- 단 벽은 K번까지 부수고 지나갈 수 있고, 낮에만 부술 수 있다.

 

즉 이제는 낮, 밤도 기록해야 한다.

 

💚16954 움직이는 미로 탈출

헷갈리지 않게 초마다 미로를 만든다.

8초까지만 벽을 준비하면 된다. 8초 이후에는 벽이 모두 사라지기 때문이다.

 

만약 각각 미로를 만들기 싫으면 A[r -t][c]로 빈칸인지, 벽인지 파악 가능하다.

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
bool check[8][8][9];
// 제자리 이동도 포함
int dx[] = {0, 0, -1, 1, -1, 1, 1, -1, 0};
int dy[] = {-1, 1, 0, 0,-1, 1, -1, 1,0};
int n = 8;
bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}
int main() {
    vector<string> a(n);

    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }

    queue<tuple<int, int, int>> q;
    check[7][0][0] = true;
    q.push({7, 0, 0});
    bool ans = false;
    while(!q.empty()) {
        int x, y, t;
        tie(x, y, t) = q.front();
        q.pop();
        if(x == 0 && y == 7) ans = true;
        for(int k = 0;k < 9;k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            // 8초 이후에는 벽이 모두 사라지기 때문
            int nt = min(t + 1, 8);
            if(inside(nx, ny)) {
                // 현재 nx에 있는 위치의 칸의 t초 전 위치를 통해 벽이 내려올지 파악
                if(nx - t >= 0 && a[nx - t][ny] == '#') continue;
                // 현재 nx에 있는 위치의 칸의 (t + 1)초 전 위치를 통해 벽이 내려올지 파악
                if(nx - t - 1 >= 0 && a[nx - t - 1][ny] == '#') continue;
                if(check[nx][ny][nt] == false) {
                    // 방문 표시
                    check[nx][ny][nt] = true;
                    q.push({nx, ny, nt});
                }
            }
        }
    }
    cout << (ans ? 1 : 0) << '\n';
    return 0;
}

✅ 3055 탈출

먼저 물이 언제 차는지 미리 구해놓은 다음에 고슴도치를 그 다음에 이동시킨다.

위 움직이는 미로와 상당히 유사한 문제다.

시간이 촉박해서 이건 패스하였다.

 

 

✅ 16236 아기상어

거리가 가장 가까운 물고리를 찾을 때, 즉 지나야하는 칸의 개수의 최소값을 구할 때 BFS를 써야한다.

BFS마다 O(N^2)이라는 시간 복잡도가 소요된다.

그러한 BFS를 최대 O(N^2) 반복한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
int dx[] = {0,0, 1, -1};
int dy[] = {1, -1, 0,0};
int n;

bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}
tuple<int, int, int> bfs(vector<vector<int>> &a, int sx, int sy, int size) {
    // 먹을 수 있는 물고기의 소요 거리, x좌표, y좌표 저장
    vector<tuple<int, int, int>> ans;
    // 거리 기록을 위해 -1로 초기화
    vector<vector<int>> d(n, vector<int>(n, -1));
    queue<pair<int, int>> q;
    q.push({sx, sy});
    d[sx][sy] = 0;
    while(!q.empty()) {
        int x, y;
        tie(x, y) =q.front();
        q.pop();
        for(int k = 0;k < 4;k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            // 배열 인덱스 및 중복 방문 확인
            if(!inside(nx, ny) || d[nx][ny] != -1) continue;
            bool moved = false;
            bool eat = false;

            // 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다.
            // 그 외의 칸은 지나갈 수 있다.
            if(a[nx][ny] == 0) moved = true;
            else if(a[nx][ny] < size) {
                moved = eat = true;
            }
            // 크기가 같은 물고기는 먹을 수는 없지만 그 물고기가 있는 칸은 지나갈 수 있다.
            else if(a[nx][ny] == size) {
                moved = true;
            }

            if(moved) {
                q.push({nx, ny});
                d[nx][ny] = d[x][y] + 1;
                if(eat) {
                    ans.push_back({d[nx][ny], nx, ny});
                }
            }
        }
    }

    if(ans.empty()) {
        return make_tuple(-1, -1, -1);
    }
    // 만약 여러 개의 물고기를 먹을 수 있으면 가장 좌상단 물고기를 먹는다.
    sort(ans.begin(), ans.end());
    return ans[0];


}
int main() {
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n, 0));
    int x, y;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            cin >> a[i][j];
            // 아기 상어 위치 파악
            if(a[i][j] == 9) {
                tie(x, y) = make_pair(i, j);
                a[i][j] = 0;
            }
        }
    }

    int ans = 0;
    int size = 2;
    int exp = 0;
    while(true) {
        int nx, ny, dist;
        tie(dist, nx, ny) = bfs(a, x, y, size);
        if(dist == -1) break;
        a[nx][ny] = 0;
        ans += dist;
        exp += 1;
        // 아기 상어가 자신의 크기와 같은 수의 물고기를 먹으면 크기가 1 증가
        if(size == exp) {
            size++;
            exp = 0;
        }
        // 아기 상어 위치 갱신
        tie(x, y) = make_pair(nx, ny);
    }

    cout << ans << '\n';
    return 0;
}

 

💚6087 레이저 통신

거울을 설치한다는 것은 직선의 방향을 바꾸는 것이라고 볼 수 있다.

거울의 개수는 두 C를 연결하는 데 필요한 직선의 최소 개수 - 1

 

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;
int n, m;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
int main() {
    cin >> m >> n;
    vector<string> a(n);
    int sx, sy, ex, ey;
    sx = sy = ex = ey = -1;
    for(int i = 0;i < n;i++){
        cin >> a[i];
        for(int j = 0;j < m;j++){
            if(a[i][j] == 'C') {
                if(sx == -1) {
                    sx = i;
                    sy = j;
                }
                else {
                    ex = i;
                    ey = j;
                }
            }
        }
    }

    vector<vector<int>> d(n, vector<int>(m, -1));
    queue<pair<int, int>> q;
    d[sx][sy] = 0;
    q.push({sx, sy});
    while(!q.empty()) {
        int x, y;
        tie(x, y) = q.front();
        q.pop();
        for(int k = 0;k < 4;k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            while(inside(nx, ny)) {
                // 벽에 부딪히면 종료
                if(a[nx][ny] == '*') break;
                if(d[nx][ny] == -1) {
                    // 방문 표시 겸 꺾는 횟수 표시
                    // 이전 방향 전환 횟수 + 1 기록
                    d[nx][ny] = d[x][y] + 1;
                    q.push({nx, ny});
                }
                nx += dx[k];
                ny += dy[k];
            }
        }
    }

    cout << d[ex][ey] - 1 << '\n';
    return 0;
}

💚1963 소수 경로

에라토스테네스의 체를 활용해 소수 판별을 한다.

그리고 필요한 변환의 수를 별도의 배열을 통해 기록해둔다.

#include <iostream>
#include <cstring>
#include <queue>
#include <string>
#include <algorithm>

using namespace std;

bool prime[10001];
bool c[10001];
int d[10001];
int change(int num, int index, int digit) {
    // 맨 앞자리 0은 불가능
    if(index == 0 && digit == 0) return -1;
    string s = to_string(num);
    s[index] = digit + '0';
    return stoi(s);
}
int main() {
    // 에라토스테네스의 체
    for(int i = 2;i <= 10000;i++) {
        if(prime[i] == false) {
            for(int j = i * i;j <= 10000;j += i) {
                prime[j] = true;
            }
        }
    }

    for(int i = 2;i <= 10000;i++) {
        prime[i] = !prime[i];
    }

    int t;
    cin >> t;
    while(t--) {
        int n, m;
        cin >> n >> m;
        memset(c, false, sizeof(c));
        memset(d, 0, sizeof(d));

        // 최초의 소수부터 시작
        d[n] = 0;
        c[n] = true;
        queue<int> q;
        q.push(n);
        while(!q.empty()) {
            int now = q.front();
            q.pop();
            for(int i = 0;i < 4;i++) {
                for(int j = 0;j <= 9;j++) {
                    int next = change(now, i, j);
                    if(next != -1) {
                        if(prime[next] && c[next] == false) {
                            q.push(next);
                            d[next] = d[now] + 1;
                            c[next] = true;
                        }
                    }
                }
            }
        }
        cout << d[m] << '\n';
    }


}

 

💚10026 적록색약

앞선 벽부수기 문제에서의 그룹짓기와 매우 유사한 문제다.

차이점은 알파벳이 다른 경우도 같은 그룹으로 처리해야한다는 점이다.

queue 밖에서 새로운 그룹이 시작되므로 queue에 처음으로 push할 때를 카운트하면 된다.