[백준/Baekjoon] 2665 미로만들기 C++ :: BFS & Dijkstra

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

2665번: 미로만들기

---

1. Logic

vis 배열에 해당 좌표까지 오는데 바꾼 최소 방의 갯수를 저장하면서 다익스트라와 비슷한 방식으로 풀이해주면 된다

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int n;

int graph[51][51];
int vis[51][51];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void bfs() {
    queue<pair<int, int>> q;
    
    q.push({0, 0});
    vis[0][0] = 0;
    
    while(!q.empty()) {
        int x = q.front().second;
        int y = q.front().first;
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            
            if(graph[ny][nx]) {
                if(vis[ny][nx] > vis[y][x]) {
                    vis[ny][nx] = vis[y][x];
                    q.push({ny, nx});
                }
            }
            else {
                if(vis[ny][nx] > vis[y][x] + 1) {
                    vis[ny][nx] = vis[y][x] + 1;
                    q.push({ny, nx});
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(vis, 0x3f3f3f3f, sizeof(vis));
    
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        string str;
        cin >> str;
        for(int j = 0; j < n; j++) {
            graph[i][j] = str[j]-'0';
        }
    }
    
    bfs();
    
    cout << vis[n-1][n-1];
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐