BOJ[백준] - 2593 - 엘리베이터

 

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

(1) BFS를 사용한 해결 방법입니다.

(2) 아시다시피 BFS는 모든 정점간의 가중치가 1이거나 모두 똑같은 경우에 사용하기 좋습니다.

각 엘리베이터내에서는 몇층이든 관계없이 그냥 한 번에 이동하는 설정입니다. 따라서 층을 정점 번호로 하여

관계를 설정해 줍시다..

(3) 자세한 설명은 코드안에 주석으로 써놓았습니다. (각 엘리베이터마다 1개씩 dummy 정점 만든 부분을 보시기 바랍니다..)

(4) 문제에서는 출력에 엘리베이터 번호를 요구하고 있지만 엘리베이터 번호가 필요없다면, dummy 정점을 만들 필요가 없습니다.

(5) 또한 path를 요구하는게 아니라면 경로찾기를 거꾸로 b부터 시작할 필요도 없겠지요 ^^

// Elevator problem : resolved with BFS, only <cstdio>
#include <cstdio>
 
// instead of vector
typedef struct node
{
   int d;
   struct node *next;
} NODE;
 
const int MXN = 100100;
int go[MXN + 1], dist[MXN + 1], q[MXN + 1], h, t;
NODE adj[MXN + 1];
 
void add(int idx, int a)
{
   NODE *t = &adj[idx];
   while(t->next != NULL)
      t = t->next;
 
   if(t->d == 0)
   {
      t->d = a;
      t->next = NULL;
   }
   else
   {
      t->next = new NODE;
      t->next->d = a;
      t->next->next = NULL;
   }
}
 
/* in this given example,
 elevator   no1 - 4, 7, 10
            no2 - 7, 12
            no3 - 4, 8, 12
 
let's add a dummy node for every evelator as follows
 elevator   no1 13(1+n) - 4, 7, 10
            no2 14(2+n) - 7, 12
            no3 15(3+n) - 4, 8, 12

then, you can make a linked list array for BFS (the last array index will be n + m)
Please note that all the stroies must be conneted with only dummy node.
It means..  the path of (10 to 8) will be 10 - (13) - 4 - (15) - 8.
[4] 13 -> 15
[7] 13 -> 14
[8] 15
[10] 13
[12] 14 -> 15
[13] 4 -> 7 -> 10
[14] 7 -> 12
[15] 4 -> 8 -> 12

if a = 10 and b = 8, it would be better to start with b because it's easier way to track the path.
(Path tree)
           8         depth 1 (dist in the code)
           |
           15        depth 2
          / | 
         4  12       depth 3
       /     |
      13     14      depth 4
     / |
    7  10            depth 5

Also, go[] array has the index of their parent,
go[10] = 13, go[13] = 4, go[4] = 15, go[15] = 8, go[8] = 0
*/
int main()
{
   int n, m;
   scanf("%d %d", &n, &m);
   for(int i = 1, x, y; i <= m; i++)
   {
      scanf("%d %d", &x, &y);
      for(int j = x; j <= n; j += y)
         add((n + i), j), add(j, (n + i));
   }
 
   int a, b;
   scanf("%d %d", &a, &b);
   for(int i = 1; i <= n + m; i++) 
      dist[i] = -1;
 
   dist[b] = 0;
   q[t++] = b;
   while(h != t) 
   {
      NODE *node = &adj[q[h]];
      while(1)
      {
         if(dist[node->d] == -1)
         {
            q[t++] = node->d;
            dist[node->d] = dist[q[h]] + 1;
            go[node->d] = q[h];
         }
         if(node->next != NULL)
            node = node->next;
         else
            break;
      }
      h++;
   }
   printf("%d\n", dist[a] / 2);
   for(int i = go[a]; i; i = go[go[i]])
      printf("%d\n", (i - n));
   return 0;
}

 

문제해결 아이디어를 다른 블로그들 구경하다가 봤는데 어느 블로그인지 다시 찾지를 못하여.. 출처를 남기지 못했습니다. ㅜ