프로그래머스 - 미로 탈출

Start -> Lever , Lever -> Exit 를 각각 탐색하여 최단경로의 합을 찾는 문제

깊이우선탐색을 활용할까 했지만 구현 실력이 부족해서 너비우선탐색을 활용하기로 했다.

구현에는 문제가 없었으나 따라오는 세가지 잘못때문에 시간이 오래걸렸다.

1. 단순 구현 오류: findTarget 의 반환값을 x, y 반대로 반환하여 문제가 발생함
2. 성급한 판단 오류: map이 항상 정사각형 형태를 띌 것이라 예측함.
3. 시간 지체: q.push()가 작동하는 것 때문에 해당 조건문의 오류만 찾으려고 시도함.

풀이

#include <string>
#include <vector>
#include <queue>
using namespace std;

int xSize, ySize;

// target의 좌표를 pair(x,y)로 반환
pair<int,int> findTarget(vector<string> maps, char target) {
    for(int i=0; i<maps.size(); i++) {
        int pos = maps[i].find(target);

        if (pos != string::npos) {
            return make_pair(pos,i);
        }
    }
}

// index가 map 안에 있는지 확인
bool indexInBound(int x, int y) {
    return 0 <= x && x < xSize && 0 <= y && y < ySize;
}

// origin -> dest 너비우선탐색 
int bfs(vector<string> maps, char origin, char dest) {
    vector<vector<int>> route(ySize, vector<int>(xSize, -1));
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};

    queue<pair<int,int>> q;
    q.push(findTarget(maps, origin));
    route[q.front().second][q.front().first] = 0;

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

        // find destination
        if (maps[y][x] == dest) return route[y][x];

        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (!indexInBound(nx,ny)) continue; // index: out of bound
            if (route[ny][nx] != -1) continue; // already visited

            if (maps[ny][nx] != 'X') { // can cross
                q.push(make_pair(nx,ny));
                route[ny][nx] = route[y][x]+1;
            }
        }
    }

    return -1;
}

int solution(vector<string> maps) {
    xSize = maps[0].length();
    ySize = maps.size();

    // S to L 너비우선탐색
    int dist1 = bfs(maps, 'S', 'L');

    // L to E 너비우선탐색
    int dist2 = bfs(maps, 'L', 'E');

    if (dist1 == -1 || dist2 == -1) return -1;

    return dist1 + dist2;
}

알게된 내용

1. String[i] 는 char
2. typeid(int).name() 으로 자료형 확인 가능