자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 그래프 최단거리 (BFS)

 

https://hyejin.tistory.com/1264

자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 경로 탐색 (인접리스트) DFS

-> 이전 문제 풀이 

 

 

13. 그래프 최단거리 (BFS)

설명

다음 그래프에서 1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하세요.

 

 

입력 설명

첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다.

그 다음부터 M줄에 걸쳐 연 결정보가 주어진다.

 

 

출력 설명

1번 정점에서 각 정점으로 가는 최소 간선수를 2번 정점부터 차례대로 출력하세요.

 

 

입력 예제 1

6 9

1 3

1 4

2 1

2 5

3 4

4 5

4 6

6 2

6 5

 

 

출력 예제 1 

2 : 3

3 : 1

4 : 1

5 : 2

6 : 2

 

 

문제 풀이 1 

public class GraphShortestDistance
{
   static int n, m = 0;
   static ArrayList<ArrayList<Integer>> graph;
   
   Queue<Integer> Q = new LinkedList<>();
   
   public int BFS(int v)
   {
      int L = 0; // root node level
      Q.offer(1);
      
      while (!Q.isEmpty())
      {
         int len = Q.size();
         for (int i = 0; i < len; i++)
         {
            int cur = Q.poll();
            if (cur == v) {
               return L;
            }else {
               for (int nv : graph.get(cur))
               {
                  if (nv == v) {
                     Q = new LinkedList<>();
                     return L + 1;
                  }
                     Q.offer(nv);
               }
            }
         }
         L++;
      }
      
      return L;
   }
   
   public static void main(String[] args)
   {
      GraphShortestDistance graphShortestDistance = new GraphShortestDistance();
      Scanner scanner = new Scanner(System.in);
      n = scanner.nextInt();
      m = scanner.nextInt();
      graph = new ArrayList<>();
      
      for (int i = 0; i  <= n; i++)
      {
         graph.add(new ArrayList<>());
      }
      
      for (int i = 0; i < m; i++)
      {
         int a = scanner.nextInt();
         int b = scanner.nextInt();
         
         graph.get(a).add(b);
      }
      
      for (int i = 2; i<= n; i++)
      {
         int result = graphShortestDistance.BFS(i);
         System.out.println(i + " : " + result);
      }
   }
}

👩‍💻: 위의 풀이는 내가 푼 풀이인데 나는 BFS 로 푼다고 하니 최단 거리를 level로 생각해서 풀었다. 

-> 이런식으로 1번 정점에서 시작해서 2번 정점까지의 최단 거리 구하고, 

1번 정점에서 시작해서 3번정점까지의 최단 거리 구하고... 

 

1️⃣

static int n, m = 0;
static ArrayList<ArrayList<Integer>> graph;

Queue<Integer> Q = new LinkedList<>();

그래서 먼저 n에는 입력받은 정점의 수를 저장하고, m에는 입력받은 간선의 수를 저장해줬다.

그리고 이번에도 인접리스트를 사용해서 문제를 풀 것이기 때문에 Arraylist<Integer> 를 저장하는 Arraylist를 만들어줬다. 

BFS 문제를 풀 때는 Queue를 사용하기 때문에 Q도 선언해줬다.

(근데 BFS 를 푼다면 무조건 Queue를 사용하는지는 아직 모르겠다.) 

 

 

1️⃣

for (int i = 0; i  <= n; i++)
{
   graph.add(new ArrayList<>());
}

for (int i = 0; i < m; i++)
{
   int a = scanner.nextInt();
   int b = scanner.nextInt();
   
   graph.get(a).add(b);
}

 

-> 그 다음에는 graph에 n + 1 개 만큼 Arraylist<Integer>를 만들어줘야 하기 때문에 반복문을 n+1만큼 돌면서 리스트를 생성해준다. 

그리고 m 만큼 반복문 돌면서 graph에 저장을 해주고, 

 

for (int i = 2; i<= n; i++)
{
   int result = graphShortestDistance.BFS(i);
   System.out.println(i + " : " + result);
}

BFS를 2 부터 n까지 돌면서 BFS 메서드를 호출해서 받은 최단 거리를 출력하도록 했다. 

 

 

 

2️⃣

public int BFS(int v)
{
   int L = 0; // root node level
   Q.offer(1);
   
   while (!Q.isEmpty())
   {
      int len = Q.size();
      for (int i = 0; i < len; i++)
      {
         int cur = Q.poll();
         if (cur == v) {
            return L;
         }else {
            for (int nv : graph.get(cur))
            {
               if (nv == v) {
                  Q = new LinkedList<>();
                  return L + 1;
               }
                  Q.offer(nv);
            }
         }
      }
      L++;
   }
   
   return L;
}

최단 거리를 레벨로 구할 것이기 때문에 먼저 L 변수를 0으로 초기화 해주고, Q 에 1 값을 먼저 offer 해준다. (문제가 1번 정점에서 다른 정점으로의 최단 거리이므로 시작은 무조건 1번 정점임) 

 

그리고 이제 while문은 queue 가 비어있지 않을 때까지 수행해주면 된다. 

Q의 사이즈를 len 이라는 변수에 저장해주고, (레벨 L에 해당하는 정점 노드의 개수) 

for문을 통해 len 만큼 돌면서 Q 를 꺼내는데 cur 값이 v와 같다면 (최단 거리를 구하고자 하는 정점과 같다면) 그 자리에서 return L 해주면 되고, 아니라면 graph에서 이제 cur 값을 꺼내서(이제 레벨 하나 +1되는 거임)  nv가 v 가 같은지 확인한다. 

만약 같으면 L +1 해서 리턴해주는데 이때 Q 에 남아있는 값이 있으면 다음 1번 정점부터의 최단 거리 구할 때 빈 Q 가 아니게 되므로 Q 를 다시 초기화해준다. 

nv가 v가 아니라면 그냥 Q 에 offer 해주면 된다. 

 

같은 레벨에 들어있던 Q를 모두 꺼냈다면 반복문을 종료하고 L ++ 해서 다음 레벨로 넘어가면 된다. 

 

 

 

-> 이런식으로 해서 1번 정점에서 2번 정점으로 가는 최단 거리를 구한 것이고, 

3번, 4번, 5번, 6번 정점도 동일하게 수행해주면 된다. 

 

 

🙄 근데 내가 푼 문제는 갔던 노드를 확인안해서 동일한 노드를 또 방문하고 있다..! 

이 부분을 수정해서 풀어야할 듯 하다.. .

 

 

 

문제 풀이 2

public class GraphShortestDistance2
{
   static int n, m;
   static ArrayList<ArrayList<Integer>> graph;
   static int[] ch, dis;
   
   public void BFS(int v)
   {
      Queue<Integer> queue = new LinkedList<>();
      ch[v] = 1;
      dis[v] = 0;
      queue.offer(v);
      
      while (!queue.isEmpty())
      {
         int cv = queue.poll();
         for (int nv : graph.get(cv))
         {
            if (ch[nv] == 0) { // 방문 안했는가 ?
               ch[nv] = 1;
               queue.offer(nv);
               dis[nv] = dis[cv] + 1;
            }
         }
      }
   }
   
   public static void main(String[] args)
   {
      GraphShortestDistance2 graphShortestDistance2 = new GraphShortestDistance2();
      Scanner scanner = new Scanner(System.in);
      n = scanner.nextInt();
      m = scanner.nextInt();
      graph = new ArrayList<>();
      
      for (int i = 0; i <= n; i++)
      {
         graph.add(new ArrayList<>());
      }
      ch = new int[n + 1];
      dis = new int[n + 1];
      
      for (int i = 0; i < m; i++)
      {
         int a = scanner.nextInt();
         int b = scanner.nextInt();
         
         graph.get(a).add(b);
      }
      
      graphShortestDistance2.BFS(1);
      
      for (int i = 2; i<= n; i++)
      {
         System.out.println(i + " : " + dis[i]);
      }
      
   }
}

👾 : 강사님은 레벨로 문제를 풀지 않고 배열을 사용해서 문제를 완전!!! 간단하게 푸셨다.. 

 

 

(밑에 그림은 강의 보고 내가 캡쳐한 그림) 

먼저 dis 라는 배열을 하나 n+1 로 만들어서 각각에는 1번 정점에서 해당 인덱스 정점에 최단 거리를 저장한다. 

ex) dis[3]의 의미는 1번 정점에서 3번 정점으로 가는 최단 거리를 의미한다. 

 

1번 정점에서 3번, 4번 정점의 최단 거리는 1이므로 1을 저장해준다. 

dis[3] = dis[1] + 1 

dis[4] = dis[1] + 1 

nv 는 v에 연결된 다음 노드 (정점)을 말한다. 

그리고 v에는 현재 노드이다. 

-> 1번 정점에서 갈 수 있는 정점들의 길이를 밑에 공식으로 해서 구할 수 있다. 

dis[nv] = dis[v] + 1 

 

그럼 이제 3번 노드 먼저 보면 3번 노드는 4번 노드로 향하는데 4번 노드는 이미 방문 중이기 때문에 패스한다. 

다음 4번 노드는 5번, 6번 노드와 연결되어 있으므로 

dis[5] = dis[4] + 1; 

dis[6] = dis[4] + 1; 해주면 된다. 

 

 

 

마지막으로 5번 노드는 연결된 정점이 없으므로 넘어가고, 6번 노드는 2번, 5번 노드로 향하는데 

5번 노드는 이미 방문 중이므로 넘어가고, 2번 노드로 간다. 

dis[2] = dis[5] + 1; 

 

이렇게 하면 1번 노드에서 각 노드 정점까지의 최단 거리를 구한 dis 배열을 얻게 되고, 

이 배열을 메인에서 반복문을 통해 출력해주면 된다. 

 

0️⃣

static int n, m;
static ArrayList<ArrayList<Integer>> graph;
static int[] ch, dis;

 

n, m, graph는 나와 동일하고, 강사님은 ch, dis  static int 배열을 만들어줬다. 

 

 

1️⃣

for (int i = 0; i <= n; i++)
{
   graph.add(new ArrayList<>());
}
ch = new int[n + 1];
dis = new int[n + 1];

for (int i = 0; i < m; i++)
{
   int a = scanner.nextInt();
   int b = scanner.nextInt();
   
   graph.get(a).add(b);
}

graphShortestDistance2.BFS(1);

for (int i = 2; i<= n; i++)
{
   System.out.println(i + " : " + dis[i]);
}

그리고 main 메서드에서 입력받은 n을 통해 ch와 dis 배열을 n+1로 초기화해준다. (인덱스 0은 넘어가기 위해서) 

BFS 메서드를 1로 지정해서 dis 배열에 1번 정점에서 다른 정점의 최단 거리를 저장하고, 

이 배열을 for문을 통해 출력 예시에 맞게 출력해주면 된다. 

 

2️⃣

public void BFS(int v)
{
   Queue<Integer> queue = new LinkedList<>();
   ch[v] = 1;
   dis[v] = 0;
   queue.offer(v);
   
   while (!queue.isEmpty())
   {
      int cv = queue.poll();
      for (int nv : graph.get(cv))
      {
         if (ch[nv] == 0) { // 방문 안했는가 ?
            ch[nv] = 1;
            queue.offer(nv);
            dis[nv] = dis[cv] + 1;
         }
      }
   }
}

 

그리고 BFS 너비 우선 탐색으로 하기 위한 Queue를 선언해주고, ch[v] 즉 ch[1] = 1, dis[1] = 0 으로 초기화해준다. 

dis[1]을 0으로 하는 이유는 1번 노드 자신이기 때문에 거리는 0이다! 

다음 queue에 1 노드를 offer 해준다. 

 

while문을 queue가 비어있지 않을때까지 반복해서 수행해준다. 

queue에서 꺼낸 현재 노드를 cv라고 하고, 

cv의 노드에서 갈 수 있는 노드를 알기 위해서 graph에서 get해서 노드들을 반복문을 통해 꺼낸다. 

이때 cv에서 다음값 nv가 방문하지 않은 노드이면 (ch[nv] == 0) ch[nv]를 1로 변경해주고, queue에 offer 해준다. 

그리고 dis[nv]에 dis[cv] + 1 값을 저장해준다.