[백준 14940] - 쉬운 최단거리 c++

문제

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

14940번: 쉬운 최단거리

 

접근 방법

BFS문제다.

코드를 줄이려 꼼수쓰지 않고, 코드가 길어지더라도

최대한 정석적으로 풀려고 노력했다.

 

코드

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

struct ground {
    int r;
    int c;
    int count;
};

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

int main() {
    
    int n, m;
    cin >> n >> m;
    vector<vector<int> > arr(n, vector<int>(m, 0));
    int startX;
    int startY;
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 2) {
                startX = i;
                startY = j;
            }
        }
    }
    deque<ground> myqueue;
    vector<vector<bool> > visit(n, vector<bool>(m, false));
    vector<vector<int> > result(n, vector<int>(m, -1));
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (arr[i][j]) result[i][j] = -1;
            else result[i][j] = 0;
        }
    }
    ground first; first.r = startX; first.c = startY; first.count = 0;
    myqueue.push_back(first);
    visit[startX][startY] = true;
    result[startX][startY] = 0;
    while(!myqueue.empty()) {
        ground x = myqueue.front();
        myqueue.pop_front();

        for (int i=0;i<4;i++) {
            int nx = x.r + dx[i];
            int ny = x.c + dy[i];
            if (nx >= n || ny >= m || nx < 0 || ny < 0) continue;
            if (!visit[nx][ny] && arr[nx][ny]) {
                ground next;
                next.r = nx; next.c = ny; next.count = x.count + 1;
                result[nx][ny] = next.count;
                visit[nx][ny] = true;
                myqueue.push_back(next);
            }
        }
    }
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            cout << result[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

 

개선할 점

문제를 제대로 보지 않아서 계속 틀렸다. visit 체크를 안해줘서 한 번 틀렸다. 

마지막에 시간 초과가 나서,

디버깅할려고 for문 안에 cout 넣어논 거 삭제하니까 성공했다.