[백준] 14940번

못가는 부분은 -1처리 해야하는지 몰랐다. 알았으면 굳이 visited를 만들 필요가 없을 듯하다.

괜히 시간복잡도만 올라간듯.

이건 O(n*m)또는 O(n)걸린다.

위 이유는 결국 1 dimension으로 보면 n = n*m으로 볼 수 있기 때문

#include <iostream>
#include <sstream>
#include <vector>
#include <map>


int main() {
    int n, m;
    std::cin >> n >> m;
    std::ostringstream os;
    std::vector<std::vector<int>> map(n+2, std::vector<int>(m+2, 0));
    std::vector<std::vector<int>> distance(n+2, std::vector<int>(m+2, 0));
    std::map<std::pair<int, int>, int> visited;
    std::vector<std::pair<int, int>> queue;
    std::pair<int, int> start;

    for (int i = 1; i < n+1; i++) {
        for (int j = 1; j < m+1; j++) {
            std::cin >> map[i][j];
            if (map[i][j] == 2) {
                start = {i, j};
            }
        }
    }

    queue.push_back(start);
    visited[start] = 1;
    while (!queue.empty()) {
        std::pair<int, int> current = queue.front(); queue.erase(queue.begin());
        map[current.first][current.second] = 0;
        if (map[current.first+1][current.second] == 1 && visited.find({current.first+1, current.second}) == visited.end()) {
            queue.push_back({current.first + 1, current.second});
            distance[current.first + 1][current.second] = distance[current.first][current.second] + 1;
            visited[{current.first + 1, current.second}] = 1;
        }
        if (map[current.first-1][current.second] == 1 && visited.find({current.first-1, current.second}) == visited.end()) {
            queue.push_back({current.first - 1, current.second});
            distance[current.first - 1][current.second] = distance[current.first][current.second] + 1;
            visited[{current.first - 1, current.second}] = 1;
        }
        if (map[current.first][current.second+1] == 1 && visited.find({current.first, current.second+1}) == visited.end()) {
            queue.push_back({current.first , current.second+1});
            distance[current.first ][current.second+1] = distance[current.first][current.second] + 1;
            visited[{current.first , current.second+1}] = 1;
        }
        if (map[current.first][current.second-1] == 1 && visited.find({current.first, current.second-1}) == visited.end()) {
            queue.push_back({current.first , current.second-1});
            distance[current.first ][current.second-1] = distance[current.first][current.second] + 1;
            visited[{current.first , current.second-1}] = 1;
        }
    }
    

    for (int i = 1; i < n+1; i++) {
        for (int j = 1; j < m+1; j++) {
            if (map[i][j] == 1) {
                distance[i][j] = -1;
            }
        }
    }
    
    for (int i = 1; i < n+1; i++) {
        for (int j = 1; j < m+1; j++) {
            os << distance[i][j] << " ";
        }
        os << std::endl;
    }

    std::cout << os.str();
    return 0;
}