[백준] 1260 DFS와 BFS

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

1260번: DFS와 BFS

 

이제 확실히 DFS, BFS에 대해서 좀 익숙해진 것 같다. DFS 부분 같은 경우에는 Stack을 사용할까도 고민해봤는데 이렇게 하면 따로 정렬해주는 부분을 구현해야 해서 그냥 재귀로 해결했다.

---

문제 및 입출력

 

---

코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main
{
        public static void bfs(int[][] graph, boolean[] visit, int start)
        {
                Queue<Integer> q = new LinkedList<Integer>();
                start--;
                visit[start] = true;
                q.add(start);

                while(!q.isEmpty())
                {
                     start = q.peek();
                     System.out.println((q.poll()+1) + " ");

                     for(int i=0; i<graph[start].length; i++)
                     {
                          if(start!=i && graph[start][i]==1 && !visit[i])
                          {
                               visit[i] = true;
                               q.add(i);
                          }
                     }
                }
            }
            // 재귀를 사용한 dfs
            public static void dfs(int[][] graph, boolean[] visit, int start)
            {
                 start--;
        
                 if(visit[start])
                 {
                      return;
                 }
        
                 visit[start] = true;
                 System.out.println((start+1) + " ");
        
                 for(int i=0; i<graph[start].length; i++)
                 {
                      if(graph[start][i]==1 && !visit[i])
                      {
                           dfs(graph, visit, i+1);
                      }
                 }
            }
            public static void main(String[] args)
            {
                 Scanner sc = new Scanner(System.in);
                 int n = sc.nextInt();
                 int m = sc.nextInt();
                 int v = sc.nextInt();
        
                 int[][] graph = new int[n][n];
                 boolean[] visit = new boolean[n];
        
                 for(int i=0; i<m; i++)
                 {
                      int start = sc.nextInt();
                      int end = sc.nextInt();
            
                      graph[start-1][end-1] = 1;
                      graph[end-1][start-1] = 1;
                 }
        
                 dfs(graph, visit, v);
                 System.out.println();
                 Arrays.fill(visit, false);
                 bfs(graph, visit, v);
            }
     }