[프로그래머스/C++] 튜브의 소개팅 (2017 카카오코드 본선)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제를 보고 어떤 값을 기준으로 priority_queue를 사용하거나 BFS로 풀면 되겠다는 생각이들었다.

그런데 priority_queue를 사용하면 정렬하는데 시간이 걸린다.

 

게다가 내가 return 할 답은 거리가 가장 짧은 값 중에서 대화시간이 가장 짧은 값이기 때문에 거리를 기준으로 정렬을 할 것이라면, BFS를 이용하면 된다.

 

그래서 BFS로 문제를 풀었다.

 

BFS를 이용하면 항상 원점에서 이동한 거리가 짧은 값이 queue에서 먼저 나온다.

그러므로 이를 이용해 특정 지점에 방문할 때 마다 가지치기를 해, 쓸모없는 경우들을 가지치기 해 주었다.

 

가지치기를 하기 위해서 visited라는 2차원 배열을 만들어 이동거리, 대화시간 값을 저장한다.

그리고 특정 좌표로 이동 할 때, visited에 있는 값과 비교해 queue에 넣을지 말지를 정한다.

 

두 값을 저장하는 이유는 단순히 이동거리가 빠른 경우만 queue에 넣으면 대화시간이 s를 넘는 경우가 생길 수 있다.

오히려 이동거리가 먼 경우에 대화시간 s를 넘기지 않고 목적지에 도달하는 경우가 생길 수 있기 때문에 대화시간이 짧은 경우도 queue에 넣어 비교해야한다.

 

그러므로 다음과 같이 가지치기를 해 queue에 넣는다.

 

1. visited의 값과 비교했을 때, 이동거리가 멀지만 대화시간이 짧은 경우

 

위에서 언급했듯이 대화시간이 s를 넘지 않아야 한다는 제약조건이 있기 때문에, 거리가 짧은 값만 비교하면 안된다.

거리가 멀지만 먼 거리를 이동해 목적지에 도착해야하는 경우가 생길 수 있어 queue에 넣어준다.

 

2. visited의 값과 비교했을 때, 이동거리가 멀고 대화시간이 긴 경우

 

이 경우는 queue에 삽입할 필요가 없다. 구해야 하는 값은 이동거리가 짧으면서 대화시간이 짧은 값이기 때문이다.

 

3. visited의 값과 비교했을 때, 거리가 짧은 경우

 

visited에 저장된 값과 비교했을 때, 거리가 짧은 경우는 첫 방문 밖에 없다.

왜냐하면 BFS로 탐색을 하기 때문에 항상 visited에 저장된 값보다 이동거리가 같거나 큰 값이 queue에 들어있다.

(queue의 특징인 선입 선출)

 

이후 queue에서 나온 값이 m-1, n-1 지점에 도달했을 때, 이동거리가 가장 짧으면서 대화시간도 적은 값을 저장하도록 하면 된다. (대화시간 s를 초과하지 않는 값들만)

 

 

​

[아이디어 정리]

1. BFS를 이용해 현재 이동거리가 짧은 값들이 먼저 나오게 한다.
2. 2차원 vector를 만들어 이동거리, 대화시간 값을 저장하고 이를 비교해 가지치기한다.
3. 최종 목적지인 m-1, n-1에 도달하면 이동거리가 가장 짧으면서 그 중에 대화시간이 가장 적은 값을 저장한다.
4. 2차원 벡터의 m-1, n-1에 저장된 값을 return한다.

 

 

Code

 

 

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

int dy[4]={0,1,0,-1};
int dx[4]={1,0,-1,0};
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, int s, vector<vector<int>> time_map) {
    vector<int> answer(2);
    vector<vector<pair<long long,long long>>>visited(m,vector<pair<long long, long long>>(n,make_pair(2500,10000000000))); // 거리, 시간 가지치기용
    visited[0][0]=make_pair(-1,10000000000);
    queue<vector<long long>> q; // y, x, 거리, 시간
    vector<long long> nv(4,0),tempV;
    q.push(nv);
    int ny, nx; 
    while(!q.empty())
    {
        nv=q.front();
        q.pop();
        if (nv[0]==m-1&&nv[1]==n-1) //도착점에 도달했다면, 더이상 진행할 필요 x 값 비교만 하면 된다.
        {
            if (visited[nv[0]][nv[1]].first>=nv[2]&&nv[3]<=visited[nv[0]][nv[1]].second)
            {
                visited[nv[0]][nv[1]].first=nv[2];
                visited[nv[0]][nv[1]].second=nv[3];                
            }
            continue;
        }
        if (visited[nv[0]][nv[1]].first<nv[2]&&visited[nv[0]][nv[1]].second<nv[3])
        {
            // 만약 q에서 꺼낸 값이 visited에 저장된 값보다 거리와 시간이 둘다 좋지 않다면 진행할 필요X
            continue;
        }
        for (int i=0; i<4; i++)
        {
            ny=nv[0]+dy[i], nx=nv[1]+dx[i];
            if (ny>=0&&ny<m&&nx>=0&&nx<n&&time_map[ny][nx]!=-1) //테이블이 없는지
            {
                long long ttt=nv[3]+time_map[ny][nx];
                if (visited[ny][nx].second>ttt&&ttt<=s)
                {// 나중에 들어오는 vector는 거리가 더 길다, 시간을 비교하면 됨
                    if (ny!=m-1||nx!=n-1) //마지막 노드는 위에서 비교하므로 값을 여기서 갱신할 필요 X
                    {
                        visited[ny][nx].first=nv[2]+1;
                        visited[ny][nx].second=nv[3]+time_map[ny][nx];
                    }
                    tempV=nv;
                    tempV[0]=ny,tempV[1]=nx,tempV[2]=nv[2]+1,tempV[3]=nv[3]+time_map[ny][nx];
                    q.push(tempV);
                }
            }
        }
    }
    answer[0] = visited[m-1][n-1].first;
    answer[1] = visited[m-1][n-1].second;

    return answer;
}

 

---

문제를 보자마자 풀이가 빠르게 생각난 문제였다.

옛날에 만들어진 문제라 그런지 난이도가 Level4보다는 Level3에 가까운 문제였던 것 같다.

 

프로그래머스