백준 2151번: 거울 설치 (C++)

접근

https://www.acmicpc.net/problem/2151

2151번: 거울 설치

처음에는 DFS 알고리즘을 이용하여 진행해 나가면서 !이 나올때마다

1. 해당 위치를 '.'으로 바꾸고 직진하고 거울 수 그대로 진행
2. 꺾고 꺾는 방향에 따라 '/' 혹은 '|'로 수정 후 거울 수 +1 하고 진행

계산을 진행해주면서 목적지에 도달할 때까지 계산하고, 목적지에 도달 시 해당 거울 수를 저장하여 문제를 풀었다.

DFS 를 이용한 코드(풀이 시간 안에는 들어오지만 시간이 많이 걸림)

#include <iostream>

using namespace std;

#define endl '\n'
#define MAX_N 51
#define INF 987654321

struct Info {
    int r;
    int c;
};

int N, ans = INF;
char MAP[MAX_N][MAX_N];

int dr[] = {0, 1, 0, -1};
int dc[] = {1, 0, -1, 0};
Info Door[2];

bool MapOut(int r, int c) {
    return (r < 0 || N <= r || c < 0 || N <= c);
}

void dfs(int r, int c, int dir, int mirror) {
    if (ans <= mirror) return;
    if (MAP[r][c] == '*') {
        return;
    } else if (r == Door[1].r && c == Door[1].c) {
        ans = mirror;
        return;
    } else if (r == Door[0].r && c == Door[0].c) {
        return;
    } else if (MAP[r][c] == '!') {
        MAP[r][c] = '.';
        dfs(r, c, dir, mirror);
        MAP[r][c] = '/';
        dfs(r, c, dir, mirror + 1);
        MAP[r][c] = '|';
        dfs(r, c, dir, mirror + 1);
        MAP[r][c] = '!';
    } else if (MAP[r][c] == '.') {
        if (MapOut(r + dr[dir], c + dc[dir])) return;
        dfs(r + dr[dir], c + dc[dir], dir, mirror);
    } else if (MAP[r][c] == '/') {
        int nd;
        if (dir == 0) {
            nd = 3;
        } else if (dir == 1) {
            nd = 2;
        } else if (dir == 2) {
            nd = 1;
        } else if (dir == 3) {
            nd = 0;
        }
        if (MapOut(r + dr[nd], c + dc[nd])) return;
        dfs(r + dr[nd], c + dc[nd], nd, mirror);
    } else if (MAP[r][c] == '|') {
        int nd;
        if (dir == 0) {
            nd = 1;
        } else if (dir == 1) {
            nd = 0;
        } else if (dir == 2) {
            nd = 3;
        } else if (dir == 3) {
            nd = 2;
        }
        if (MapOut(r + dr[nd], c + dc[nd])) return;
        dfs(r + dr[nd], c + dc[nd], nd, mirror);
    }
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    cin >> N;
    int k = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> MAP[i][j];
            if (MAP[i][j] == '#') {
                Door[k++] = {i, j};
            }
        }
    }
    for (int i = 0; i < 4; i++) {
        int nr = Door[0].r + dr[i];
        int nc = Door[0].c + dc[i];
        if (MapOut(nr, nc)) continue;
        dfs(nr, nc, i, 0);
    }

    cout << ans << endl;

    return 0;
}

 

하지만 계산 시간이 오래걸려서 해결할 수 있는 방법이 있을까 생각해보다보니, !에 거울을 설치하고 난 뒤에 거울의 뒷면을 생각할 필요가 없다는 것을 깨달았다. 해당 거울의 뒷면을 이용할 경우, 애초에 해당 거울을 반대 방향으로 꺾도록 설치하는 것이 거울 수에서 이득이기 때문이다. 즉, 거울을 설치한 후 해당 위치에 다시 돌아오는 경우는 추가 계산할 필요가 없다는 것을 적용했더니 bfs 알고리즘으로 푸는 것이 더 어울릴것 같아 bfs 알고리즘으로 변경하여 풀었다.

처음 문의 위치에서 탐색을 시작하되 빛이 이동할 수 있는 모든 위치를 직진하면서 거울의 설치 위치가 나오면 큐에 추가해준다. 거울 위치는 visited 배열을 이용하여 한 곳의 거울 위치를 큐에 두번 추가할 수 없도록 중복 제거해주었다.

0-1 bfs 방법으로도 동일하게 풀 수 있을 것이라는 생각이 들었다.

코드

#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

#define endl '\n'
#define MAX_N 51
#define INF 987654321

struct Info {
    int r;
    int c;
};

int N, ans = -1;
char MAP[MAX_N][MAX_N];
int visited[MAX_N][MAX_N];

int dr[] = {0, 1, 0, -1};
int dc[] = {1, 0, -1, 0};
Info Door[2];

bool MapOut(int r, int c) {
    return (r < 0 || N <= r || c < 0 || N <= c);
}

void bfs() {
    memset(visited, 0, sizeof(visited));
    queue<pair<int, int>> Q;
    Q.push(make_pair(Door[0].r, Door[0].c));
    visited[Door[0].r][Door[0].c] = 1;
    while (Q.empty() == 0) {
        int size = Q.size();
        ans++;
        for (int i = 0; i < size; i++) {
            int r = Q.front().first;
            int c = Q.front().second;
            Q.pop();
            for (int j = 0; j < 4; j++) {
                int dist = 1;
                while (1) {
                    // 처음 위치에서 직선으로 쭉 진행
                    int nr = r + dr[j] * dist;
                    int nc = c + dc[j] * dist;
                    if (MapOut(nr, nc) || MAP[nr][nc] == '*') {
                        // 벽을 만나거나 집 바깥으로 나갈 경우 중단
                        break;
                    } else if (MAP[nr][nc] == '!' && visited[nr][nc] == 0) {
                        // 도달하지 않았던 거울 위치가 나올 경우 큐에 추가
                        Q.push(make_pair(nr, nc));
                        visited[nr][nc] = 1;
                    } else if (MAP[nr][nc] == '#' && visited[nr][nc] == 0) {
                        // 다른 문에 도달할 경우 탐색 종료
                        return;
                    }
                    dist++;
                }
            }
        }
    }
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    cin >> N;
    int k = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> MAP[i][j];
            if (MAP[i][j] == '#') {
                Door[k++] = {i, j};
            }
        }
    }
    bfs();
    cout << ans << endl;

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!