DFS, BFS

이번 주에는 dfs , bfs 문제들을 풀어보려고 한다.

BFS 는 큐, DFS 는 스택 으로 구현하면 된다, 이 정보들을 가지고 사실 dfs 로 구현은 거의 하지 않았다.

 

지금까지 풀었던 문제들은 대부분 구현 방식이 다음과 같다.

 

1. 큐에 시작 지점을 넣고 방문 표시를 남긴다.

2. 큐에서 원소를 꺼내, 상하좌우 인접 칸을 살핀다.

3. 이전 방문 이력이 없다면 삽입하고, 방문 표시 남긴 후 큐에 삽입한다.

4. 큐가 빌 때 까지 반복한다.

 

이번에 푼 문제는 2차원 배열 상에서의 dfs 가 아니였다. +1, -1, x2 를 이동할 수 있는 일차원 배열 상의 문제였다.

 

이 경우 if 문을 3번 사용해서 각각을 확인 해 줄 수 있는데, 이 경우 continue 를 해버려서 이 후 경우를 아예 체크하지 않는

경우를 피해주어야 한다.

 

이렇게 배열에 넣고 for 문으로 돌리는게 속이 편할 수도 있다.

  next[0] = cur+1;
    next[1] = cur-1;
    next[2] = cur*2;

    for (int i = 0; i <3; i++)
    {
      new_pos = next[i];
      if (new_pos < 0 || new_pos > 200000) continue;
      if (visited[new_pos] != 0) continue;
      if (new_pos == k)
      {
        cout<<visited[cur] + 1 << "\n";
        return 0;
      }
      q.push(new_pos);
   }

 

이번에 푼 문제는 숨바꼭질 3이라는 문제이다.

 

이번에 visited 배열에 방문 순서를 저장하여 풀었는데, 이 부분이 문제가 된 것 같다. 

앞으로는 visited 배열은 bool 값으로 만들어 0,1 값만 저장될 수 있도록 하고,

몇번째 방문인지는 배열을 따로 만들어 저장한다던가, pair 에 가지고 다닌다던가 하는게 좋겠다.

 

그리고, 이번 문제의 경우에는 기존 BFS 문제 풀던 것처럼 풀면 풀리지 않는 문제라고 하더라.

 

그 이유가 무엇인고 하니, BFS 문제는 모든 방문 경로에 대한 가중치가 같을 때에만 가능하다는 것이다.

 

만약 방문 가능한 방법 중 비용이 다른 방법이 있다면, 그 때는 일반적인 BFS 를 통해 풀 수 없다.

 

그렇다면 가중치가 있을 때, 그래프에서 탐색은 어떻게 진행해야 할까??

 

-> 다익스트라 알고리즘

 

https://blog.encrypted.gg/1037

[실전 알고리즘] 0x1D강 - 다익스트라 알고리즘

다익스트라 알고리즘은 음수 가중치를 가진 간선이 없을 때 이용 가능하다. -> 음수 가중치가 있을 경우에는 벨만 포드 알고리즘을 이용한다.

 

다익스트라 구현은 BFS 와 큰 차이가 없다. 

1. 큐 대신 우선순위 큐를 사용한다.

2. 큐 안에 정점 번호, 해당 정점 까지 최단 거리 를 넣는다.