[C++] 백준 16137번: 견우와 직녀

🔗 문제

16137번: 견우와 직녀

16137번: 견우와 직녀

 

 

 

문제 정리

• (0, 0)에서 (N-1, N-1)로 최소 이동 시간 구하기
  • N (2 ≤ N ≤ 10)
• 상하좌우로 이동할 수 있으며 한칸 당 1분 소요
• 맵 구성요소
  • 1: 이동할 수 있는 일반적인 땅
  • 0: 건널 수 없는 절벽
  • 2 이상의 수: 적혀있는 수 만큼의 주기를 가지는 오작교
• 오작교 특징
  • M(2 ≤ M ≤ 20)분 주기에만 오작교가 생성되어 절벽을 건너갈 수 있다.

 

🖍 풀이

 

문제 꼼꼼히 보기

오작교는 이처럼 매우 불안정하므로, 견우는 안전을 위해 두 번 연속으로 오작교를 건너지는 않기로 했다.

연속으로 map[i][j] > 0인 구역에 갈 수 없다. → 오작교 다룰 때 bool 로 연속으로 건넜는지 봐야겠다.

 

까마귀와 까치는 조금이라도 견우를 더 도와주기 위해, 절벽을 정확히 하나 골라 주기가 M분인 오작교를 하나 더 놓아 주기로 했다.단, 이미 오작교를 짓기로 예정한 절벽에는 오작교를 하나 더 놓을 수 없고,

M주기 오작교를 0 위치에 하나 넣을 수 있다. → 절벽 만나면 bool로 이미 하나 놨는지 안 놨는지 확인해야겠다.

 

아래와 같이 절벽이 가로와 세로로 교차하는 곳에도 오작교를 놓을 수 없다.

내 위치가 i , j 이면 내 상하좌우에 절벽이 2개 이상 있으면 오작교를 놓을 수도 없으니 아예 못 가는 길이구나.

 

---

풀이 과정

간단한 풀이 과정을 작성했는데 한번 읽고 소스 코드를 직접 보는 게 이해가 빠를 것 같다.

 

 

1. check_cliff() 오작교를 설치할 수 없는 절벽 구역 표기
   • 상하 / 좌우 이렇게 따로 절벽 개수를 세어서 교차로인지 확인해주었다.
2. BFS()

• BFS에 사용할 queue의 타입은 좌표의 위치마다 필요한 정보가 많아 struct로 구성해주었다.

struct Info 
{ 
    int x, y, time = 0; 
    bool bridge = false; // 오작교는 연속해서 건널 수 없다. 이미 건넜으면 true 
    bool built = false; // 오작교는 임의로 1번만 설치할 수 있다. 설치했으면 true 
};

• int check[2][MAX][MAX]
  • 다리 설치 유무에 따른 (0, 0) ~ (x, y)까지 이동하는 데 걸린 최소 시간 저장

 

💡 재방문 확인을 하지 않는 이유

보통 BFS로 최소 이동시간을 구할 때는 재방문확인으로 시간을 줄이는데 이 문제는 그러면 안된다.

오작교 주기를 기다리는 시간이 있기 때문에 먼저 도착했다고 최소 시간을 가지는 것이 아니기 때문이다.

그래서 check[다리설치유무][x][y]를 최소값으로 갱신해주며 진행하는 것이다.

 

쉽게 생각해보면 지나가다가 마주친 절벽에 다리를 설치하거나 기다렸다 오는거보다 그냥 빙 돌아서 오는게 빠를 수도 있잖아요 🙂

 

 

• 📋 도움이 된 예제

  8 2 
  1 1 1 1 0 1 1 1 
  1 1 0 1 0 1 0 1 
  0 0 0 1 1 1 0 1 
  0 0 0 0 0 0 0 1 
  0 0 0 0 0 1 0 1 
  0 0 0 0 0 1 1 1 
  0 0 0 0 0 0 0 10 
  0 0 0 0 0 0 1 1
  
  //answer : 20
  

  🖇️ 출처 https://www.acmicpc.net/board/view/42365

 

💾  소스

#include <iostream>
#include <queue>

const int INF = 1e9;
const int MAX = 20 + 1;

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

int N, M, answer = INF;
int map[MAX][MAX];
int check[2][MAX][MAX];

bool isValid(const int x, const int y)
{
    if(x<0 || x>=N || y<0 || y>=N)
        return false;
    return true;
}

enum STATE
{
    CLIFF = 0,
    GROUND = 1,
		BLOCK = -1 // 절대 지나갈 수 없음
};

struct Info
{
public:
    Info() = default;
    Info(const int _x, const int _y, const int _time = 0, 
            const bool _bridge = false, const bool _built = false)
         :x(_x), y(_y), time(_time), 
        bridge(_bridge), built(_built){};

    int x, y, time = 0;
    bool bridge = false;
    bool built = false;
};

//////////////////////////////////////////////////////////

void check_cliff()
{
    // 절벽이 교차로라 오작교를 설치 못하는 구역인지 확인하는 함수
    // 설치 못 하면 절대 지나갈 수 없는 곳이니 BLOCK 로 표기
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<N; ++j)
        {
            if(map[i][j] != 0) continue;

            int r=0, c=0;
            for(int d=0; d<2; ++d)
                if(isValid(i+dx[d], j+dy[d]) && map[i+dx[d]][j+dy[d]] != GROUND)
                    ++r;

            for(int d=2; d<4; ++d)
                if(isValid(i+dx[d], j+dy[d]) && map[i+dx[d]][j+dy[d]] != GROUND)
                    ++c;

            if(r>=1 && c>=1) map[i][j] = BLOCK;
        }
    }
}

void BFS()
{
    std::queue<Info> q;
    q.push({0, 0, 0, false, false});
    check[0][0][0] = 0;

    while(!q.empty())
    {
        auto info = q.front(); q.pop();

        if(info.x == N-1 && info.y == N-1)
        {
            answer = (answer < info.time ? answer : info.time);
            continue;
        }

        for(int d=0; d<4; ++d)
        {
            int x = info.x + dx[d];
            int y = info.y + dy[d];

            if(!isValid(x, y) || map[x][y] == BLOCK)
                continue;
        
            if(map[x][y] == GROUND) // 땅
            {
                if(check[info.built][x][y] > info.time+1)
                {
                    check[info.built][x][y] = info.time+1;
                    q.push({x, y, info.time+1, false, info.built});
                }
            }
            else if(map[x][y] == CLIFF) // 절벽
            {
                if(info.built || info.bridge) continue;

                // 주기를 기다렸다가 감
                int time = 0;
                if((info.time + 1) % M !=0)
                    time = M - (info.time + 1) % M;

                time += info.time + 1;

                if(check[1][x][y] > time)
                {
                    check[1][x][y] = time;
                    q.push({x, y, time, true, true});
                }
            }
            else if(map[x][y] > 1) // 오작교 설치 예정
            {
                if(info.bridge) continue;

                // 주기를 기다렸다가 감
                int time = 0;
                if ((info.time + 1) % map[x][y] != 0)
                    time = map[x][y] - (info.time + 1) % map[x][y];

                time += info.time + 1;

                if (check[1][x][y] > time)
                {
                    check[1][x][y] = time;
                    q.push({x, y, time, true, info.built});
                }
            }
        }

    }
}

void input()
{
    std::cin >> N >> M;
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<N; ++j)
        {
            std::cin >> map[i][j];
            check[0][i][j] = check[1][i][j] = INF;
        }
    }
}

int main()
{

    input();

    check_cliff();
    BFS();

    std::cout << answer;

    return 0;
}