강 건너기 문제

※이 글은 사람이 10명 이하일 때의 알고리즘입니다.

Large 문제의 해법은 <== 여기 있습니다.

 

Code SASA: 1287

https://code.sasa.hs.kr/problem.php?id=1287

SASA OJ

n명의 사람이 최대 2명까지 탈 수 있는 배를 타고 강을 건너는 상황이다. 

사람들마다 배를 타고 강 끝까지 가는 시간이 다르고, 2명이 같이 탔을 때는 더 오래 걸리는 사람의 시간만큼 걸린다.

목표는 사람들이 모두 강 건너편으로 갈 때까지 걸리는 최소 시간이다.

 

구조화 방법

상태는 처음 위치를 0, 강 건너편을 1로 둔 다음, 사람들의 위치, 배의 위치를 비트로 생각하여 비트마스킹 한다.

 

(사람 1) (사람 2) ... (사람 n) ( 배 )  이런 식으로 비트마스킹

ex) 사람이 처음에 3명이 있다면

처음 상태 ==> 0000 

원하는 상태 ==> 1111  이 된다.

 

탐색 알고리즘

n이 7 이하이기 때문에 사람들이 분포될 수 있는 경우의 수는 2^7 * 2(배의 위치) = 256 으로 매우 작다. 그렇기 때문에 브루트 포스 (DFS)로 충분히 해결될 수 있을 것이라 보았지만 웬걸, 83퍼에서 시간 초과가 걸리고 말았다.

다시 생각해보니 256개의 정점이 있는 것이더라.. 일반적인 DFS로 풀 경우 지수함수에 비례하는 시간이 걸리므로 시간 초과가 날 수 밖에 없다.

그럼 지금 구해야 하는 것은 가중치 그래프에서의 최단 거리이다. 그렇다면 역시 다익스트라 알고리즘을 사용하자.

 

아래 풀이를 이해하기 위해서는 다익스트라 알고리즘에 대한 기본적인 이해가 필요하다.

다익스트라 알고리즘은 https://jason9319.tistory.com/307 ACM-ICPC 상 탈 사람님의 블로그를 참고 바란다.

[다익스트라 알고리즘 문제 : (가망 없는 최종단계 길찾기) https://code.sasa.hs.kr/problem.php?id=2280 ]

 

시행착오

최종 코드를 구현했는데, 이번에는 웬걸 시간초과가 아니라 메모리 초과가 났다.

알고보니, 다익스트라 알고리즘을 잘못 이해하고 있는 부분이 있었다.

1. 현재 있는 정점이 다른 정점을 탐색할 때, 거리 정보가 갱신되는 정점만 우선순위 큐에 새로 넣는 것이다.

즉 ( d+ dis[cur] < dis[next] ) 일 경우에만 갱신과 함께 우선순위 큐 삽입을 진행한다.

2. pq에 삽입된 정점을 볼 때, 이미 구해진 거리가 삽입된 정점의 거리 ( pair 을 말함) 보다 작으면 그 정점은 현재 정점이 될 수 없다. 

이미 그 정점에서 더 작은 거리의 탐색이 이루어졌는데 , 그 이상의 탐색은 무쓸모이다. 

 

2가지 사실을 밑에 있는 블로그를 통해 깨닫고 나서, AC를 받았다.

http://www.secmem.org/blog/2019/01/09/wrong-dijkstra/

잘못 구현한 다익스트라 알고리즘 저격하기

 

정점 간 상관관계

 최단 경로에서는 갈 때는 항상 2명이 타고 , 올 때는 1명이 탄다. 

갈 때 1명이 타고 가는 것, 올 때 2명이 타고 오는 것은 정말 무의미한 시간 낭비이기 때문이다.

즉, 배의 위치가 0이면 2명이 타고 가는 정점과 연결되고

배의 위치가 1이면 1명이 타고 오는 정점과 연결된다. 

 

비트 다루기

id & 1 --> 배의 위치 ( 0이면 출발지 ,1이면 도착지)

id & (1<<i) --> 사람의 위치 (0이면 출발지 ,1이면 도착지)

alt= id ^((1<<i)+(1<<j)+1) 사람 2명의 위치와 배를 이동시킴.

 

최종 코드

#include<stdio.h>
#include<queue>
#include<algorithm>
#define INF 99999
using namespace std;
typedef struct _node{
    int bit,dist;
}node;
struct cmp{ //연산자 오버로딩 
    bool operator()(node a1, node a2){
            if(a1.dist==a2.dist)
                return a1.bit<a2.bit;
        return a1.dist > a2.dist;
    }
};
priority_queue<node,vector<node>,cmp> pq;
int n,arr[10],visit[300],dist[300],start,final,pre[300];
int Dijkstra(){
    for(int i=1;i<=n;i++){
        int bit =(1<<i)+1;
        dist[bit] = arr[i];
    }
    start=0,final=(1<<n+1)-1;
    visit[0]=1; dist[0]=0;
    pq.push({0,0});
    while(!pq.empty()){
        int id=pq.top().bit,cost=pq.top().dist;
        pq.pop();
        if(dist[id]<cost) continue;
        visit[id]=1;
        if(!(id&1)){
            for(int i=1;i<n;i++){
                for(int j=i+1;j<=n;j++){
                    if(!(id&(1<<i))&&!(id&(1<<j))){
                        int alt= id ^((1<<i)+(1<<j)+1),d;
                        if(visit[alt]==0){
                            d=dist[id]+max(arr[i],arr[j]);
                            if(d<dist[alt]){
                                pq.push({alt,d});
                                dist[alt]=d;
                                pre[alt]=id;
                            }
                        }
                    }
                }
            }
        }else{
            for(int i=1;i<=n;i++){
                if(id & (1<<i)){
                    int alt=id^((1<<i)+1),d;
                    if(visit[alt]==0){
                        d=dist[id]+arr[i];
                        if(d<dist[alt]){
                            pq.push({alt,d});
                            dist[alt]=d;
                            pre[alt]=id;
                        }
                    }
                }
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",arr+i);
    for(int i=0;i<=300;i++) dist[i]=INF;
    Dijkstra();
    printf("%d",dist[final]);
}
/**************************************************************
    Problem: 1287
    User: pentagon03
    Language: C++
    Result: 정답
    Time:0 ms
    Memory:1180 kb