(매일 BOJ) C++ 14940번 쉬운 최단거리

이번 문제는 14940번 쉬운 최단거리다

문제 요약

• 입력 격자: 0 = 벽(못 감), 1 = 지나갈 수 있음, 2 = 시작점
• 출력 규칙:
  • 시작점은 0 (거리 0)
  • 갈 수 있는 칸은 최단거리
  • 도달 불가한 1은 -1
  • 0은 그대로 0

접근법

• 각 칸을 정점, 4방향 인접 칸을 간선으로 보면 무가중치 그래프 최단거리 → BFS가 정답
• 지도(graph) 자체를 거리 저장용으로 덮어쓰기
  • 시작점(2)은 0으로 바꾸고 시작
  • 이동 가능한 1만 큐에 넣으며 graph[nx][ny] = graph[cur] + 1로 거리 누적
• BFS 종료 후, 한 번도 방문 안 된 1을 -1로 치환
• 복잡도
  • 시간: O(N*M) — 각 칸 최대 한 번씩 큐에 들어간다
  • 공간: O(N*M) — 방문배열 / 큐가 격자 크기와 같은 오더

거리 배열 dist를 따로 만들지 않고, 한 배열로 끝내니 메모리·코드가 둘 다 단순함

작성코드

#include <bits/stdc++.h>
using namespace std;

int N,M;
int fourway_x[4] = {1,-1,0,0};
int fourway_y[4] = {0,0,1,-1};
void BFS(vector<vector<int>> & graph, pair<int, int> startpoint);
int main (void){
    cin >> N >> M;
    pair<int, int> startpoint;
    vector<vector<int>> graph(N,vector<int>(M));
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> graph[i][j];
            if(graph[i][j] == 2) startpoint = {i,j};
        }
    }

    BFS(graph,startpoint);

    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cout << graph[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

void BFS(vector<vector<int>> & graph, pair<int, int> startpoint){
    vector<vector<bool>> visited(N,vector<bool> (M,false));
    queue<pair<int,int>> q;
    q.push(startpoint);
    visited[startpoint.first][startpoint.second] = true;
    graph[startpoint.first][startpoint.second] = 0;

    while(!q.empty()){
        int current_n = q.front().first;
        int current_m = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++){
            int next_n = fourway_x[i] + current_n;
            int next_m = fourway_y[i] + current_m;

            if(next_n >= 0 && next_n < N && next_m >= 0 && next_m < M && !visited[next_n][next_m] && graph[next_n][next_m] == 1){
                q.push({next_n,next_m});
                visited[next_n][next_m] = true;
                graph[next_n][next_m] = graph[current_n][current_m] + 1;
            }
        }
    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(!visited[i][j] && graph[i][j] == 1) graph[i][j] = -1;
        }
    }
}