[프로그래머스] 코딩테스트 연습문제 - Lv2. 미로 탈출 C++

- 문제

직사각형 격자 미로에서 탈출하려고 함. 각 칸은 통로 또는 벽.

벽은 통과 불가능하며, 통로 중 한 칸에는 미로 탈출 문이 존재. 그러나, 문은 레버를 당겨야만 열 수 있으며, 레버도 통로들 중 한 칸에 존재.

즉, 출발 지점에서 먼저 레버 칸으로 이동해서 레버 당긴 후에 미로 탈출 문 칸으로 이동해야 함.

아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있으며, 미로 한 칸 이동은 1초 소요.

최대한 빠르게 미로를 빠져나가는데 걸리는 시간 구하기.

 

- 입력

문자열 배열 maps : 미로

 

- 출력

탈출에 필요한 최소 시간 리턴

(단, 탈출 불가능 시에는 -1 리턴)

 

- 제약 사항

5 <= maps 길이 <= 100

(S : 시작 / E : 출구 / L : 레버 / O : 통로 / X : 벽)

시작 지점과 출구, 레버는 항상 다른 곳에 1개 씩만 존재

출구 레버가 당겨지지 않아도 지나갈 수 있고, 모든 통로, 출구, 레버, 시작점은 여러 번 통과 가능

 

---

 

문제이해

"시작 -> 레버" & "레버 -> 탈출구" 이동을 위한 최단 비용을 구해야 함.

 

접근방법

bfs를 사용해서 maps 상에 시작 위치에서 끝 위치까지 갈 수 있는 경로들을 queue에 담아 탐색.

만약 maps 범위를 넘거나, 통로가 아니라 지나갈 수 없거나, 이미 방문한 곳이라면 해당 위치는 continue로 지나감.

최종적으로 시작 위치에서 끝 위치까지 도달했다면, cost를 리턴함.

만약, 도달 가능한 경로가 없었다면, -1을 반환.

최종적으로 S에서 L로, L에서 E로 이동했을 때의 cost 2개를 합해서 반환.

 

주의 사항

시작에서 끝 위치로 도달하지 못했을 때에 -1을 반환해야 함.

 < 테스트 케이스 예시 >

["SXXOX", "EXXXL", "OOXOO", "OXXXX", "OOOOO"]

답 : -1

 

코드

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

using namespace std;

struct Node {
    int y;
    int x;
    int cost;
};

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

int visited[101][101] = { 0, };

int bfs(vector<string> maps, int sy, int sx, int ey, int ex) {

    queue<Node> q;
    memset(visited, 0, sizeof(visited));

    Node start;
    start.y = sy;
    start.x = sx;
    start.cost = 1;
    q.push(start);

    visited[start.y][start.x] = 1;

    while (!q.empty()) {

        Node now = q.front();
        q.pop();

        if (now.y == ey && now.x == ex) {
            return now.cost - 1;
        }

        for (int i = 0; i < 4; i++) {

            int ny = now.y + dy[i];
            int nx = now.x + dx[i];

            if (ny < 0 || nx < 0 || ny >= height || nx >= width)
                continue;

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

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

            visited[ny][nx] = now.cost + 1;
            q.push({ ny, nx, now.cost + 1 });

        }

    }
    
    return -1;

}
int solution(vector<string> maps) {
    int answer = 0;

    int starty, startx;
    int endy, endx;
    int levery, leverx;

    height = maps.size();
    width = maps[0].length();

    //입력
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (maps[i][j] == 'S') {
                starty = i;
                startx = j;
            }
            else if (maps[i][j] == 'L') {
                levery = i;
                leverx = j;
            }
            else if (maps[i][j] == 'E') {
                endy = i;
                endx = j;
            }
        }
    }

    //탐색
    int firstcost = bfs(maps, starty, startx, levery, leverx);

    int secondcost = bfs(maps, levery, leverx, endy, endx);

    answer = firstcost + secondcost;

    if (firstcost <= 0 || secondcost <= 0) return -1;

    return answer;
}

 

 

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스