글 읽기 - 탐색이 이상하게 됩니다.

yoonminsu0617 4년 전 0

DFS만 인접리스트로 해 봤습니다. 뭔가 잘 못됬는지 탐색이 이상하게 됩니다.

재귀로 하면 정상적으로 나옵니다..

근데 재귀가 아닌 스택을 직접 사용해 해결하고 싶습니다.
*/

문제는 해결했습니다.

83 ~ 87번 라인을 주석을 하게 되면 다른 값이 나오게 됩니다.

예제 2

3 4 5 2 1 ( DFS )

3 4 1 5 2 ( BFS )

인접 리스트로 할 때는 정렬을 해줄 필요가 있는건가요?

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

import java.util.Stack;
import java.util.Queue;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
   public static void bfs( ArrayList<Integer> a[], boolean c[], int v ) {
      Queue<Integer> q = new LinkedList<>();

      q.add( v );
      c[ v ] = true;
      
      while( !q.isEmpty() ) {
         v = q.poll();
         System.out.print( v + " " );

         for( int vv : a[ v ] ) {
            if( !c[ vv ] ) {
               q.add( vv );
               c[ vv ] = true;
            }
         }
      }
   }

   public static void dfs( ArrayList<Integer> a[], boolean c[], int v ) {
      Stack<Integer> stack = new Stack<>();
      boolean flag = true;
      
      stack.push( v );
      c[ v ] = true;
      System.out.print( v + " " );

      while( !stack.isEmpty() ) {
         int vt = stack.peek();
         flag = false;
         
         for( int vv : a[ vt ] ) {
            if( !c[ vv ] ) {
               stack.push( vv );
               System.out.print( vv + " " );
               c[ vv ] = true;
               flag = true;
               break;
            }
         }
         if( !flag ) {
            stack.pop();
         }
      }
   }
   public static void main( String[] args) throws IOException {
      BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
      StringTokenizer st = new StringTokenizer( br.readLine() );

      int N = Integer.parseInt( st.nextToken() );  // 정점 개수
      int M = Integer.parseInt( st.nextToken() );  // 간선 개수
      int V = Integer.parseInt( st.nextToken() );  // 시작할 정점

      ArrayList<Integer> a[] = ( ArrayList<Integer>[] ) new ArrayList[ N + 1 ];
      boolean c[] = new boolean[ N + 1 ];

      for( int i = 0; i <= N; ++i ) {
         a[ i ] = new ArrayList<>();
      }

      for( int i = 0; i < M; ++i ) {
         st = new StringTokenizer( br.readLine() );
         int v1 = Integer.parseInt( st.nextToken() );
         int v2 = Integer.parseInt( st.nextToken() );

         a[ v1 ].add( v2 );
         a[ v2 ].add( v1 );
      }
       /*
      for( int i = 1; i <= N; ++i ) {
         Collections.sort( a[ i ] );
      }
      */

      dfs( a, c, V );
      System.out.println();
      Arrays.fill(c, false );
      bfs( a, c, V );
      
   }
}

djm03178 4년 전 1

문제에서 정렬된 순서로 방문하라고 했으니 당연히 정렬을 해주어야 합니다.

yoonminsu0617 4년 전 0

@djm03178

"방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고"

제가 문제를 잘 읽지 않았네요 지적 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

탐색이 이상하게 됩니다.

yoonminsu0617 4년 전 0

djm03178 4년 전 1

yoonminsu0617 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말