KiTFOx's Notepad 📝

문제

거울을 설치하면 방향을 90도 회전시킬 수 있다.

*은 벽으로 뚫고 지나갈 수 없다.

거울을 최소로 설치하여서 처음 시작지점 C에서 끝지점 C에 도달할때까지 가야한다.

최소로 설치할 수 있는 거울 수를 출력하라

입력 1

7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

출력 1

3

코드

#include<iostream>
#include<algorithm>
#include<utility>
#include<queue>
#include<vector>

using namespace std;

//6087번 레이저 통신

char MAP[101][101];
int visited[101][101];
int w, h;
int arrow[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };

pair<int, int> startP, endP;
queue<pair<int,int>> cntDir;
queue < pair<int, int>> Q;
void BFS() {
    for (int i = 0; i < 4; i++) {
        Q.push(make_pair(startP.first, startP.second));
        cntDir.push(make_pair(0, i));
    }
    visited[startP.first][startP.second] = 0;

    while (Q.empty() == 0) {
        int y = Q.front().first;
        int x = Q.front().second;
        int cnt = cntDir.front().first;
        int dir = cntDir.front().second;
        Q.pop();
        cntDir.pop();
        //좌우위아래 탐색
        for (int i = 0; i < 4; i++) {
            int ny = y + arrow[i][0];
            int nx = x + arrow[i][1];
            int nCnt = cnt;

            if (nx <0 || nx >= w || ny < 0 || ny >=h) continue;
            if (MAP[ny][nx] == '*') continue;
            if (dir != i) nCnt++;
            if (visited[ny][nx] >= nCnt) {
                visited[ny][nx] = nCnt;
                Q.push(make_pair(ny, nx));
                cntDir.push(make_pair(nCnt, i));
            }
        }
    }
    cout << visited[endP.first][endP.second];
}

void input() {
    bool isFirst = true;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'C') {
                (isFirst) ? startP = make_pair(i, j) : endP = make_pair(i, j);
                isFirst = false;
            }
            visited[i][j] = 10001;
        }
    }
}

int main() {

    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> w >> h;
    
    input();
    BFS();


    return 0;
}

*간단한 해설*

void input() {
    bool isFirst = true;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'C') {
                (isFirst) ? startP = make_pair(i, j) : endP = make_pair(i, j);
                isFirst = false;
            }
            visited[i][j] = 10001;
        }
    }
}

먼저 input 함수에서 cin을 통해 MAP을 받아옵니다.

그 중 만약 C가 입력되었다면 처음인지 아닌지를 판단해서 처음이라면 startP에 해당 위치를 넣고, 처음이 아니라면 endP에 해당 위치를 넣는다.

void BFS() {
    for (int i = 0; i < 4; i++) {
        Q.push(make_pair(startP.first, startP.second));
        cntDir.push(make_pair(0, i));
    }
    visited[startP.first][startP.second] = 0;

    while (Q.empty() == 0) {
        int y = Q.front().first;
        int x = Q.front().second;
        int cnt = cntDir.front().first;
        int dir = cntDir.front().second;
        Q.pop();
        cntDir.pop();
        //좌우위아래 탐색
        for (int i = 0; i < 4; i++) {
            int ny = y + arrow[i][0];
            int nx = x + arrow[i][1];
            int nCnt = cnt;

            if (nx <0 || nx >= w || ny < 0 || ny >=h) continue;
            if (MAP[ny][nx] == '*') continue;
            if (dir != i) nCnt++;
            if (visited[ny][nx] >= nCnt) {
                visited[ny][nx] = nCnt;
                Q.push(make_pair(ny, nx));
                cntDir.push(make_pair(nCnt, i));
            }
        }
    }
    cout << visited[endP.first][endP.second];
}

탐색을 시작할 위치인 startP의 위치를 4번 Q에 옮겨담습니다. 시작 위치에서 위,아래,왼쪽,오른쪽 방향을 탐색하는 방향을 저장해줍니다. 방향이 다르다면 거울의 갯수를 더해줘야하기 때문입니다. 

그 다음 Q가 빌때까지 while문을 돌립니다. Q의 첫번째 인자를 변수에 담고 좌우위아래 탐색을 시작합니다. 탐색에서 *인 벽을 만나거나 맵을 벗어나면 탐색을 건너뛰고, 만약 가던 방향과 현재 방향이 맞지 않다면 거울을 더해줍니다. 현재 방문한 위치에서의 거울을 사용한 갯수를 visited[][] 배열에 저장하기에 만약 사용한 갯수가 현재 카운트보다 높다면 최소로 사용해야하기때문에 변경해줍니다. 이것을 끝지점에 도달할때까지 계속 반복하여서 visited[끝지점.y][끝지점.x] 의 값을 출력하면 답이 됩니다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*