[개쉬운 풀이] 백준 6087 레이저 통신 (5일차)

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

문제

 

생각

1. 처음에는 단순하게 BFS로 풀면 된다고 생각했다.

2. 또한 거울의 수는 단순하게 레이저가 꺽인 횟수라고 생각하였다. 

3. 따라서 처음 queue에 C에서 나아갈 수 있는 방향 4가지를 넣어서 시작했다.

4. 이때 queue에는 (x, y 좌표와 방향, 거울 수)가 담겨있다.

5. 다음 현재 방향과 다음 방향을 맞추어 거울의 수를 담아서 BFS를 완성하였다.

 

1. 그러나, 이 과정에서 방향 때문에 겹치는 x,y좌표가 많아지게 되면서 메모리 초과 문제가 발생하였다.

2. 따라서 isVisited를 2차원 배열이 아닌 방향을 추가한 3차원 배열로 만들어서 해결하였다.

 

결론 : BFS / DFS 문제에서 좌표뿐 만 아니라 다른 변수가 있을 때, 3차원 배열로 만드는 것이 메모리 문제를 효과적으로 해결할 수 있다.

풀이

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

// 노드 구조체 정의
struct N {
    int x, y, dir, count; // x, y: 현재 위치 / dir: 현재 방향 / count: 거울 설치 개수

    // 생성자 정의
    N(int x, int y, int dir, int count) : x(x), y(y), dir(dir), count(count) {}
};

const int MAX = 101; // 맵 크기의 최대값

int W, H; // 가로(W), 세로(H)
char map[MAX][MAX]; // 지도 정보
int isVisited[MAX][MAX][4]; // 방문 여부를 방향별로 저장 (4방향: 오른쪽, 아래, 왼쪽, 위)
vector<N> pos; // 레이저 시작점과 도착점을 저장
int dx[4] = {0, 1, 0, -1}; // x축 이동 (오른쪽, 아래, 왼쪽, 위)
int dy[4] = {1, 0, -1, 0}; // y축 이동 (오른쪽, 아래, 왼쪽, 위)

// 입력 처리 함수
void input() {
    cin >> W >> H; // 가로, 세로 입력
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> map[i][j]; // 지도 정보 입력
            for (int k = 0; k < 4; k++) {
                isVisited[i][j][k] = 1e9; // 방문 배열 초기화
            }
            if (map[i][j] == 'C') { // 레이저 시작점 또는 도착점일 경우
                pos.push_back(N(i, j, 0, 0)); // 좌표 저장
            }
        }
    }
}

// 좌표가 지도 범위를 벗어났는지 확인
bool isOut(int x, int y) {
    return x < 0 || y < 0 || x >= H || y >= W;
}

// 레이저 최소 거울 개수 계산 함수
void sol() {
    queue<N> q; // BFS를 위한 큐

    // 시작점에서 4방향으로 초기화
    for (int i = 0; i < 4; i++) {
        q.push(N(pos[0].x, pos[0].y, i, 0)); // 시작점에서 각 방향으로 이동
        isVisited[pos[0].x][pos[0].y][i] = 0; // 시작점 방문 표시
    }

    // BFS 시작
    while (!q.empty()) {
        N cur = q.front(); // 현재 노드
        
        // 현재 상태
        int x = cur.x
        int y = cur.y
        int dir = cur.dir
        int count = cur.count; 
        
        q.pop();

        // 4방향으로 이동
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i]; // 다음 x 좌표
            int ny = y + dy[i]; // 다음 y 좌표
            int nCount = count; // 거울 개수

            // 범위를 벗어나거나 장애물('*')이면 무시
            if (isOut(nx, ny) || map[nx][ny] == '*') continue;

            // 방향이 바뀌는 경우 거울 개수 증가
            if (dir != i) nCount++;

            // 새로운 상태가 기존 상태보다 효율적일 경우 갱신
            if (nCount < isVisited[nx][ny][i]) {
                isVisited[nx][ny][i] = nCount; // 방문 갱신
                if (map[nx][ny] != 'C') { // 다음 위치가 도착점이 아니라면
                    q.push(N(nx, ny, i, nCount)); // 큐에 추가
                }
            }
        }
    }

    // 도착점에서 각 방향별 최소 거울 개수 중 최솟값 찾기
    int answer = 1e9;
    for (int i = 0; i < 4; i++) {
        answer = min(answer, isVisited[pos[1].x][pos[1].y][i]);
    }

    // 결과 출력
    cout << answer << endl;
}

int main() {
    input(); // 입력 처리
    sol();   // 레이저 최소 거울 개수 계산
    return 0;
}