문제 풀이 과정을 공유하고자 한다.
문제 출처

1. 문제설명

  • 1x1 크기의 칸들로 이루어진 미로가 주어진다.
  • 각 칸은 S, E, L, O, X 중 하나로 이뤄진다.
  • 주목!
    • 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다.
  • 문제의 설명이 조금 난해한 부분이 있었다.
    • 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다.
    • 반드시 출발지->레버->출구 순으로 가야하는데
    • 이때 중간에 출구를 만나도 지나칠 수 있다는 뜻이다.



2. 알고리즘 설계

  • 다들 아시다시피, BFS 문제
  • 출발지->레버, 레버->도착지의 최단 거리를 합쳐주면 된다.
    • 출발지->도착지점이 아님.
  • 각각의 출발지는 weight를 0으로 부여한다.
    • 만약 레버에서 출구로 가는 경우,
    • 출발지->레버에서 이미 레버의 칸이 세어진다.
    • 따라서 레버->도착지에서 레버의 weight는 0으로 부여



3. 로직

  • BFS 함수 구현
    • 만약 BFS가 한번 호출되면 함수로 빼지 않아도 되지만
    • 2번 이상 호출 되는 경우는 함수로 별도 구현하는 게 좋다.
  • BFS 함수 인자로 src(출발지), dest(목적지)를 넘긴다.
    • 각각은 S->L, L->E를 넣으면 된다.

  • 만약 두 번의 함수 값 중 하나라도 -1을 리턴했다면 -1을 리턴한다.

    // BFS를 돌다가 목적지를 만난 경우
if (cur.y == dest.first && cur.x == dest.second)
  return cur.dist;

// BFS를 돌다가 목적지를 만나지 못한 경우
return -1


4. 전체 코드

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

using namespace std;
using pii = pair<int, int>;

typedef struct {
    int y, x, dist;
}pos;

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

char map[100][100];
bool visited[100][100];

int bfs(pii src, pii dest, int y_len, int x_len) {
    memset(visited, false, sizeof(visited));

    queue<pos> q;
    q.push({ src.first, src.second, 0 });
    visited[src.first][src.second] = true;

    while (!q.empty()) {
        pos cur = q.front();
        q.pop();

        if (cur.y == dest.first && cur.x == dest.second)
            return cur.dist;

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

            if (ny < 0 || nx < 0 || ny >= y_len || nx >= x_len)
                continue;
            if (visited[ny][nx] || map[ny][nx] == 'X')
                continue;

            q.push({ ny, nx, cur.dist + 1 });
            visited[ny][nx] = true;
        }
    }

    return -1;
}

int solution(vector<string> maps) {
    pii s, e, l;

    int y_len = maps.size();
    int x_len = maps[0].size();

    for (int y = 0; y < y_len; y++) {
        for (int x = 0; x < x_len; x++) {
            map[y][x] = maps[y][x];

            if (map[y][x] == 'S')
                s = { y, x };
            if (map[y][x] == 'E')
                e = { y, x };
            if (map[y][x] == 'L')
                l = { y,x };
        }
    }

    int a = bfs(s, l, y_len, x_len);
    int b = bfs(l, e, y_len, x_len);

    return (a<0 || b <0) ? -1 : a+b;
}


5. 소감

  • 평소 BFS 문제를 즐겨 풀었었다.
  • 풀이에도 꽤나 자신이 있었다. (백준 골드 3~4정도?)
  • 사실 BFS를 이용한 완전탐색 문제는 많이 풀어봤는데,
  • BFS를 두 번 이용해야 하는 문제는 처음이라 조금 헤맸다..ㅎ