프로그래머스 미로 탈출 C++

#include <string>
#include <vector>
#include <queue>

using namespace std;

struct Maze {
    int x;
    int y;
    bool lever;
};

int visited[101][101];

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

int solution(vector<string> maps) {
    int answer = 0;
    int sx, sy;

    //find starting point
    int col = maps.size();
    int row = maps[0].size();
    for (int i = 0; i < col;i++) {
        for (int j = 0; j < row ;j++) {
            if (maps[i][j] == 'S') {
                sx = j, sy = i;
                break;
            }
        }
    }

    queue<Maze> q; 
    q.push({ sx, sy, false });
    visited[sy][sx] = 1;

    // bfs
    while (!q.empty()) {
        int cx = q.front().x;
        int cy = q.front().y;
        int clever = q.front().lever;
        q.pop();

        if (clever == true && maps[cy][cx] == 'E') {
            return visited[cy][cx]-1;
        }

        for (int i = 0;i < 4;i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            bool nlever = clever;

            if (ny < 0 || nx < 0 || ny >= col || nx >= row) {
                continue;
            }
            
            if (visited[ny][nx]!=0){
                continue;
            }
            if (maps[ny][nx] == 'X') {
                continue;
            }

            if (maps[ny][nx] == 'L') {
                nlever = true;
            }

            visited[ny][nx] = visited[cy][cx] + 1;
            q.push({ nx, ny, nlever });

        }
    }
    answer = -1;
    return answer;
}

 초기 코드는 이렇게 짰는데 절반만 맞았다.

제한 사항에 이런 구절이 있다.

모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

이 부분에 대한 처리가 이 문제의 핵심 구현 사항이다.

 

이렇게 하면 visited에 대한 처리가 모호해진다. 따라서, bfs를 두번 돌리는 것이 조금 더 맞는 구현이라고 볼 수 있다.

 

 

정답 코드 : 

#include <string>
#include <vector>
#include <queue>
#include <cstring>
#include <iostream>

using namespace std;

struct Maze {
    int x;
    int y;
};

int visited[101][101];

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

int solution(vector<string> maps) {
    int answer = 0;
    int sx, sy;
    bool found_lever = false, found_exit = false;
    //find starting point
    int col = maps.size();
    int row = maps[0].size();
    for (int i = 0; i < col;i++) {
        for (int j = 0; j < row;j++) {
            if (maps[i][j] == 'S') {
                sx = j, sy = i;
                break;
            }
        }
    }

    queue<Maze> q;
    q.push({ sx, sy });
    visited[sy][sx] = 1;

    // bfs
    while (!q.empty()) {
        int cx = q.front().x;
        int cy = q.front().y;
        q.pop();

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

            if (ny < 0 || nx < 0 || ny >= col || nx >= row) {
                continue;
            }

            if (maps[ny][nx] == 'X') {
                continue;
            }

            if (visited[ny][nx] != 0) {
                continue;
            }

            visited[ny][nx] = visited[cy][cx] + 1;

            if (maps[ny][nx] == 'L') {
                sx = nx, sy = ny, dist = visited[ny][nx] - 1;
                found_lever = true;
                break;
            }

            q.push({ nx, ny });

        }
    }

    while (!q.empty()) {
        q.pop();
    }
    memset(visited, 0, sizeof(visited));
    q.push({ sx, sy });
    visited[sy][sx] = 1;

    while (!q.empty()) {
        int cx = q.front().x;
        int cy = q.front().y;
        q.pop();

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

            if (ny < 0 || nx < 0 || ny >= col || nx >= row) {
                continue;
            }

            if (maps[ny][nx] == 'X') {
                continue;
            }

            if (visited[ny][nx] != 0) {
                continue;
            }

            visited[ny][nx] = visited[cy][cx] + 1;

            if (maps[ny][nx] == 'E') {
                sx = nx, sy = ny, dist = dist + visited[ny][nx] - 1;
                found_exit = -1;
                break;
            }
            q.push({ nx, ny });
        }
    }
    if (!found_lever || !found_exit){
        answer = -1;
    }
    else{
        answer = dist;
    }
    return answer;
}