궤도

[백준] 1938번 : 통나무 옮기기 본문

💻 현생/⛓ 알고리즘

[백준] 1938번 : 통나무 옮기기

영이오 2021. 8. 18. 16:40

문제

 

풀이

 

최소 동작 횟수라고 했으니까 BFS로 풀면 될 것이고, 가로로 놓는 경우와 세로로 놓는 경우의 visited를 따로 처리해야하니까 3차원 배열로 visited를 처리해야겠다.

 

그리고 3개를 다 들고 돌아다니는건 좀 비효율적이니까...가운데에 있는 통나무 하나만 들고다니려고 한다. 왜 굳이 가운데를 쓰냐면 그게 회전할 때 편하기 때문이다.

 

통나무의 상태, 그리고 하려는 동작에 따라 체크해야하는 범위가 다르다.

가로 통나무를 UDLR 하면 1x3의 범위를 확인해야 하고,

세로 통나무를 UDLF 하면 3x1의 범위를 확인해야 하고,

T하면 3x3의 범위를 확인해야 한다.

 

이걸 하나하나 따로 처리하는건 비효율적이니까 함수로 만들어서 관리하려고 한다.

소스코드

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct info {
    int r, c, t;
};

vector<vector<char>> board;
pair<int, int> dir[4] = {{-1, 0},  //상
                         {1,  0},  //하
                         {0,  -1}, //좌
                         {0,  1}}; //우

bool promising(int N, int sr, int er, int sc, int ec) { //해당 좌표가 범위를 벗어나거나 1을 포함하는지 확인
    for (int i = sr; i <= er; i++) {
        for (int j = sc; j <= ec; j++) {
            if (i < 0 || i >= N || j < 0 || j >= N || board[i][j] == '1')
                return false;
        }
    }
    return true;
}

int bfs(int N, info start, info end) {
    queue<info> q;
    vector<vector<vector<int>>> dist(N, vector<vector<int>>(N, vector<int>(2, 0)));
    dist[start.r][start.c][start.t] = 1;
    q.push(start);
    while (!q.empty()) {
        int row = q.front().r; //행
        int col = q.front().c; //열
        int d = q.front().t; //방향
        int distance = dist[row][col][d];
        q.pop();

        if (row == end.r && col == end.c && d == end.t) //도착
            return distance - 1;
        for (int i = 0; i < 4; i++) {
            int nr = row + dir[i].first;
            int nc = col + dir[i].second;
            if (d == 0 && !promising(N, nr - 1, nr + 1, nc, nc)) //세로 모양일 때 범위 확인
                continue;
            if (d == 1 && !promising(N, nr, nr, nc - 1, nc + 1)) //가로 모양일 때 범위 확인
                continue;
            if (dist[nr][nc][d]) //방문 체크
                continue;
            dist[nr][nc][d] = distance + 1;
            q.push({nr, nc, d});
        }
        if (promising(N, row - 1, row + 1, col - 1, col + 1) && !dist[row][col][(d + 1) % 2]) { //회전
            dist[row][col][(d + 1) % 2] = distance + 1;
            q.push({row, col, (d + 1) % 2});
        }
    }
    return 0; //이동 불가
}

int main() {
    int N;
    string input;
    bool is_start = false, is_end = false;
    info start{}, end{};

    cin >> N;
    board.assign(N, vector<char>(N));
    for (int i = 0; i < N; i++) {
        cin >> input;
        for (int j = 0; j < N; j++) {
            board[i][j] = input[j];
            if (board[i][j] == 'B' && !is_start) { //시작점
                is_start = true;
                if (j + 1 < N && input[j + 1] == 'B') //가로
                    start = {i, j + 1, 1};
                else //세로
                    start = {i + 1, j, 0};
            }
            if (board[i][j] == 'E' && !is_end) { //도착점
                is_end = true;
                if (j + 1 < N && input[j + 1] == 'E') //가로
                    end = {i, j + 1, 1};
                else //세로
                    end = {i + 1, j, 0};
            }
        }
    }
    cout << bfs(N, start, end);
}

전체 소스코드다.

 

struct info {
    int r, c, t;
};

각 통나무의 상태를 저장할 구조체이다. 열, 행, 방향이다.

 

    cin >> N;
    board.assign(N, vector<char>(N));
    for (int i = 0; i < N; i++) {
        cin >> input;
        for (int j = 0; j < N; j++) {
            board[i][j] = input[j];
            if (board[i][j] == 'B' && !is_start) { //시작점
                is_start = true;
                if (j + 1 < N && input[j + 1] == 'B') //가로
                    start = {i, j + 1, 1};
                else //세로
                    start = {i + 1, j, 0};
            }
            if (board[i][j] == 'E' && !is_end) { //도착점
                is_end = true;
                if (j + 1 < N && input[j + 1] == 'E') //가로
                    end = {i, j + 1, 1};
                else //세로
                    end = {i + 1, j, 0};
            }
        }
    }

입력을 받을 때 시작점과 도착점을 찾는다.

뭐든 제일 먼저 발견된 B와 E가 제일 위에 있거나 제일 왼쪽에 있는 나무토막일테니 걔를 기준으로 한칸 오른쪽에 있거나 한칸 아래에 있는 나무토막이 가운데 나무토막이다.

 

int bfs(int N, info start, info end) {
    queue<info> q;
    vector<vector<vector<int>>> dist(N, vector<vector<int>>(N, vector<int>(2, 0)));
    dist[start.r][start.c][start.t] = 1;
    q.push(start);
    while (!q.empty()) {
        int row = q.front().r; //행
        int col = q.front().c; //열
        int d = q.front().t; //방향
        int distance = dist[row][col][d];
        q.pop();

        if (row == end.r && col == end.c && d == end.t) //도착
            return distance - 1;
        for (int i = 0; i < 4; i++) {
            int nr = row + dir[i].first;
            int nc = col + dir[i].second;
            if (d == 0 && !promising(N, nr - 1, nr + 1, nc, nc)) //세로 모양일 때 범위 확인
                continue;
            if (d == 1 && !promising(N, nr, nr, nc - 1, nc + 1)) //가로 모양일 때 범위 확인
                continue;
            if (dist[nr][nc][d]) //방문 체크
                continue;
            dist[nr][nc][d] = distance + 1;
            q.push({nr, nc, d});
        }
        if (promising(N, row - 1, row + 1, col - 1, col + 1) && !dist[row][col][(d + 1) % 2]) { //회전
            dist[row][col][(d + 1) % 2] = distance + 1;
            q.push({row, col, (d + 1) % 2});
        }
    }
    return 0; //이동 불가
}

bfs 함수다.

 

    queue<info> q;
    vector<vector<vector<int>>> dist(N, vector<vector<int>>(N, vector<int>(2, 0)));
    dist[start.r][start.c][start.t] = 1;
    q.push(start);

시작점 초기화 하고

 

    while (!q.empty()) {
        int row = q.front().r; //행
        int col = q.front().c; //열
        int d = q.front().t; //방향
        int distance = dist[row][col][d];
        q.pop();

        if (row == end.r && col == end.c && d == end.t) //도착
            return distance - 1;
        for (int i = 0; i < 4; i++) {
            int nr = row + dir[i].first;
            int nc = col + dir[i].second;
            if (d == 0 && !promising(N, nr - 1, nr + 1, nc, nc)) //세로 모양일 때 범위 확인
                continue;
            if (d == 1 && !promising(N, nr, nr, nc - 1, nc + 1)) //가로 모양일 때 범위 확인
                continue;
            if (dist[nr][nc][d]) //방문 체크
                continue;
            dist[nr][nc][d] = distance + 1;
            q.push({nr, nc, d});
        }
        if (promising(N, row - 1, row + 1, col - 1, col + 1) && !dist[row][col][(d + 1) % 2]) { //회전
            dist[row][col][(d + 1) % 2] = distance + 1;
            q.push({row, col, (d + 1) % 2});
        }
    }

while문을 돈다.

 

        int row = q.front().r; //행
        int col = q.front().c; //열
        int d = q.front().t; //방향
        int distance = dist[row][col][d];
        q.pop();

        if (row == end.r && col == end.c && d == end.t) //도착
            return distance - 1;

필요한 정보 빼오고 도착점과 비교해서 목표지점에 도착했다면 리턴한다.

그렇지 않다면...

 

        for (int i = 0; i < 4; i++) {
            int nr = row + dir[i].first;
            int nc = col + dir[i].second;
            if (d == 0 && !promising(N, nr - 1, nr + 1, nc, nc)) //세로 모양일 때 범위 확인
                continue;
            if (d == 1 && !promising(N, nr, nr, nc - 1, nc + 1)) //가로 모양일 때 범위 확인
                continue;
            if (dist[nr][nc][d]) //방문 체크
                continue;
            dist[nr][nc][d] = distance + 1;
            q.push({nr, nc, d});
        }

일단 UDLR을 해본다. d==0 그니까 세로로 놓였다면 세로 범위를 확인하고, 아니라면 가로 범위를 확인한다.

 

bool promising(int N, int sr, int er, int sc, int ec) { //해당 좌표가 범위를 벗어나거나 1을 포함하는지 확인
    for (int i = sr; i <= er; i++) {
        for (int j = sc; j <= ec; j++) {
            if (i < 0 || i >= N || j < 0 || j >= N || board[i][j] == '1')
                return false;
        }
    }
    return true;
}

범위는 이 함수에서 확인한다.

 

            if (dist[nr][nc][d]) //방문 체크
                continue;
            dist[nr][nc][d] = distance + 1;
            q.push({nr, nc, d});

범위 통과했으면 방문 체크하고 다 통과하면 큐에 넣어준다.

 

        if (promising(N, row - 1, row + 1, col - 1, col + 1) && !dist[row][col][(d + 1) % 2]) { //회전
            dist[row][col][(d + 1) % 2] = distance + 1;
            q.push({row, col, (d + 1) % 2});
        }

그 다음은 T연산이다. 그냥 제자리에서 범위 체크랑 방문 체크만 하고 큐에 넣어주면 된다.

 

    return 0; //이동 불가

이동이 불가능할 수도 있다니까 이렇게 처리하면 끝

저작자표시 비영리 변경금지
'💻 현생/⛓ 알고리즘' Related Articles more
Comments