[C++]백준 2151번 거울 설치

📌문제 링크

---

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

📌문제 설명

---

먼저 미로의 크기와 각 칸의 정보를 입력받고, 시작점과 도착점을 찾습니다. BFS를 통해 각 위치에서 네 방향으로 이동하며, 거울을 설치할 수 있는 위치에서는 방향을 바꿔가며 탐색을 진행합니다. 각 위치와 방향에 대해 최소 거울 설치 횟수를 기록하고, 도착점에 도달했을 때의 최소 거울 설치 횟수를 출력합니다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <climits>
using namespace std;

// 미로를 저장할 배열
char mp[51][51];

// 미로의 크기와 정답을 저장할 변수
int N, answer = INT_MAX, firstX = -1, firstY, secondX, secondY;

// 방문 여부를 저장할 배열
int visited[51][51][4];

// 방향을 나타내는 배열 (동, 남, 서, 북)
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

// 상태를 저장할 구조체
struct comp {
    int x, y, prevDir, prevCnt;
};

// 입력 함수
void input() {
    cin >> N; // 미로의 크기 입력
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> mp[i][j]; // 미로의 각 칸 입력
            if (mp[i][j] == '#') {
                if (firstX == -1) {
                    firstX = i;
                    firstY = j;
                } else {
                    secondX = i;
                    secondY = j;
                }
            }
        }
    }
}

// BFS 탐색 함수
void bfs() {
    queue<comp> q; // 큐 선언
    for (int i = 0; i < 4; i++) {
        q.push({firstX, firstY, i, 0}); // 시작점에서 네 방향으로 탐색 시작
        visited[firstX][firstY][i] = 0; // 시작점 방문 처리
    }

    while (!q.empty()) {
        comp cur = q.front(); // 현재 상태
        q.pop();

        int nx = cur.x + dx[cur.prevDir]; // 다음 위치
        int ny = cur.y + dy[cur.prevDir];

        if (nx < 0 || ny < 0 || nx >= N || ny >= N || mp[nx][ny] == '*') continue; // 범위를 벗어나거나 벽이면 무시

        if (visited[nx][ny][cur.prevDir] > cur.prevCnt) {
            visited[nx][ny][cur.prevDir] = cur.prevCnt; // 방문 처리
            q.push({nx, ny, cur.prevDir, cur.prevCnt}); // 큐에 추가
        }

        if (mp[nx][ny] == '!') {
            for (int i = 0; i < 4; i++) {
                if (i == (cur.prevDir + 2) % 4) continue; // 반대 방향은 무시
                if (visited[nx][ny][i] > cur.prevCnt + 1) {
                    visited[nx][ny][i] = cur.prevCnt + 1; // 방문 처리
                    q.push({nx, ny, i, cur.prevCnt + 1}); // 큐에 추가
                }
            }
        }
    }
}

// 메인 함수
int main() {
    input(); // 입력 함수 호출
    bfs(); // BFS 탐색 함수 호출
    for (int i = 0; i < 4; i++) {
        answer = min(answer, visited[secondX][secondY][i]); // 최소 거울 설치 횟수 계산
    }
    cout << answer << endl; // 결과 출력
    return 0;
}